Pounding into straw effigies
Pounding into straw effigies
Pounding into straw effigies
Five-inch, five-inch, five-inch nails!
Yi er san yi er san one two three one two three ichi ni sa~n
Yi er san yi er san one two three one two three ichi ni sa~n
Yi er san yi er san one two three one two three ichi ni sa~n
Eins, zwei, guten morgen
Yi er yi er ichi ichi ichi ichi
Hifumi hifumi hifumi hifumi hihifu
Hifumi hifumi hifumi hifumi hihifu
Hifumi hifumi hifumi hifumi hihifu
Hihihihihihihihihihihihihihihihihihihihihihihihi hifumiyo hifumiyo
Dawn to, dawn to, dawn to, dawn to, dawn to, dawn to, dawn to, dawn to
Dawn to, dawn to, dawn to, dawn to, dawn to, dawn to (I can't feel it)
Dawn to, dawn to, dawn to, dawn to, dawn to, dawn to, dawn to, dawn to
Dawn to, dawn to, dawn to, dawn to, dawn to, dawn to (It doesn't hurt)
Check it gee, check it gee, check it gee, check it gee, check it gee, check it gee, check it gee, check it gee
Ugigi- ugigi- ugigi- ugigi- kugigi- kugigi- kugigi- kugigi-
Shanghai Shanghai Shanghai Shanghai
Hourai Hourai Hourai Hourai
France Holland Tibet Kyoto London Russian Orle~ans
Hating, hating, loving (ah ah-ah ah ah-ah ah)
Who are you? Who are you? I can't be alive without you
Why is it, I wonder (ah ah-ah ah); why (why why why) don't I miss you a lot, forever?
I don't know how to work your magic
If I told you how I felt, I'd break
I'm different from you
So don't go around stealing other people's hearts that easily
A close-up future of turning (ah ah-ah ah ah-ah ah)
My distant feelings, I can't be alive without you
Why is it, I wonder (ah ah-ah ah); why (why why why) don't I believe you more, forever?
I know about that secret of yours;
It's always screaming out in the bottom of my heart
I'm not the same as you
So don't go around stealing other people's hearts so easily
---
You are given an array $a$ of length $n$ where all elements are initially $0$, a permutation $p$ of length $n$, and $q$ queries:
- `0 l r x`: Increase $a_l, a_{l+1}, ..., a_r$ by $x$.
- `1 l r x`: Increase $a_{p_l}, a_{p_{l+1}}, ..., a_{p_r}$ by $x$.
- `2 l r`: Compute the sum of $a_l + a_{l+1} + ... + a_r$.
- `3 l r`: Compute the sum of $a_{p_l} + a_{p_{l+1}} + ... + a_{p_r}$.
### Input
- The first line contains two integers $n$ and $q$.
- The next line contains a permutation $p$ of length $n$.
- The next $q$ lines each contain a query in the format described above.
### Output
- Print the result for each query of type `2` and `3` on a separate line.
### Constraints
- $1 \leq n, q \leq 10^5$
- $1 \leq l \leq r \leq n$
- $1 \le x \le 10^6$.
### Example
Input:
```
5 6
3 1 5 4 2
0 2 4 2
1 2 4 3
2 3 4
0 2 5 1
3 2 4
3 1 3
```
Output :
```
7
13
10
```
### Subtasks
- Subtask 1 ($15\\%$ of the points): $n, q \leq 10^3$.
- Subtask 2 ($15\\%$ of the points): Queries are only of type `1` and `3`.
- Subtask 3 ($15\\%$ of the points): There are at most $2$ queries of type `2` or `3`.
- Subtask 4 ($15\\%$ of the points): $l_i = l_j$ and $r_i = r_j$ if $i$ and $j$ are the same type of query.
- Subtask 5 ($40\\%$ of the points): No additional constraints.
