Given a sequence $a$ of length $n$, there are two types of operations to be performed $m$ times:
- Given $l, r, x$, for all $i$ such that $l \le i \le r$ and $a_i \neq x$, update $a_i \leftarrow a_i - x$.
- Given $l, r$, calculate the sum of $a_i$ for all $i$ such that $l \le i \le r$ and $a_i \neq 0$.
Input
The first line contains two integers $n$ and $m$.
The second line contains $n$ space-separated integers representing the sequence $a$.
The following $m$ lines each contain three or four integers:
If the input is 1 l r x, it represents a type 1 operation on the interval $[l, r]$. If the input is 2 l r, it represents a type 2 operation on the interval $[l, r]$.
This problem is forced online. All input values $l, r, x$ must be XORed with $lastans$, which is defined as the result of the previous query operation modulo $2^{20}$. If there has been no query operation yet, $lastans$ is $0$.
Output
For each type 2 operation, output a single line containing the answer modulo $2^{64}$.
Examples
Input 1
10 10 0 1 2 3 4 5 6 7 8 9 1 5 10 5 2 1 10 1 23 29 23 2 21 19 1 1048573 1048570 1048574 2 1048573 1048566 1 1048573 1048569 1048575 2 1048575 1048564 1 1048572 1048567 1048572 2 1048572 1048567
Output 1
20 18446744073709551615 18446744073709551614 18446744073709551613 18446744073709551606
Subtasks
Idea: nzhtl1477, Solution: nzhtl1477, Code: w33z8kqrqk8zzzx33, Data: w33z8kqrqk8zzzx33
For $5\%$ of the data, $n, m \le 1000$.
For $30\%$ of the data, $n, m \le 5 \times 10^4$.
For another $20\%$ of the data, $l = 1, r = n$.
For another $20\%$ of the data, $x = 1$.
For $100\%$ of the data, $1 \le n, m \le 5 \times 10^5, 0 \le a_i, x \le 10^9$.