Given an array of $N$ numbers (initially, each number is set to $0$), you need to answer $Q$ queries of $2$ types:

1 i' v': Add $v$ to the $i^{\text{th}}$ number.

2 l' r' x': Query the sum $[l,r]$ after undoing the $x$ most recent type $1$ queries (note: the undo queries are NOT persistent).

Constraints

$1\le N,Q\le 300000$

$1\le i\le N$

$1\le l\le r\le N$

$0\le v\le {10}^9$

It is guaranteed that there have been at least $x$ type $1$ queries.

Input Specification

The first line will contain $N$ and $Q$, the number of elements in the array and the number of queries.

The next $Q$ lines will contain a query from those listed above.

Note that this problem will be online enforced, meaning that input will be given in an encrypted format. To encrypt the data, the values $l,r,i,v,x$ in queries will be given as $l^{\prime }=l\oplus \text{lastAns},r^{\prime }=r\oplus \text{lastAns}$, $i^{\prime }=i\oplus \text{lastAns}$, $v^{\prime }=v\oplus \text{lastAns}$, and $x^{\prime }=x\oplus \text{lastAns}$, where $\oplus$ denotes the bitwise XOR operation. Note that $|\text{lastAns}|$ at any time is defined as the answer to the latest query. If no queries have occurred so far, $\text{lastAns}=0$.

Output Specification

Output the answer to each type $2$ query.

Sample Input (Encrypted)

5 6
1 1 5
1 5 9
2 1 5 0
2 15 11 15
1 6 7
2 4 0 5

Sample Input (Unencrypted)

5 6
1 1 5
1 5 9
2 1 5 0
2 1 5 1
1 3 2
2 1 5 0

Sample Output

14
5
16