Problem K
Kinda Free

You are given an array $A$ of length $N$ (1-indexed). You must process $Q$ queries of two types:

1. 1 l r x: For every $i$ with $l \le i \le r$, replace $A_i$ by $A_i \oplus x$ (bitwise XOR).

2. 2 l r: Compute and output $\sum _{i=l}^{r} A_i^2$.

Here, $\oplus $ denotes the XOR operator, and $A_i^2$ is the square of $A_i$.

Input

The first line contains two integers $N$ and $Q$ $(1 \leq N \leq 200000,\ 1 \leq Q \leq 200000)$.

The second line contains $N$ integers $A_1, A_2, \dots , A_N$ $(0 \leq A_i < 2^{10})$.

Each of the next $Q$ lines describes a query in one of the two formats above, with $1 \leq l \leq r \leq N$ and $0 \leq x < 2^{10}$.

Output

For every query of type 2, output a single integer: the value of

The answer always fits in a signed 64-bit integer.

Sample 1 Explanation

Initially, $A = [1,2,3,4,5]$.

1. Query 2 1 5: $1^2 + 2^2 + 3^2 + 4^2 + 5^2 = 55$.

2. Query 1 2 4 1: apply XOR with $1$ to positions $2$ through $4$:

   \[ A = [1,\ 2\oplus 1,\ 3\oplus 1,\ 4\oplus 1,\ 5] = [1,3,2,5,5]. \]

3. Query 2 2 4: $3^2 + 2^2 + 5^2 = 9 + 4 + 25 = 38$.

4. Query 2 3 3: $2^2 = 4$.

5 4
1 2 3 4 5
2 1 5
1 2 4 1
2 2 4
2 3 3

55
38
4