Dynamic Range Vector Queries

You are given n vectors \(\overrightarrow{a_1},\overrightarrow{a_2},\ldots,\overrightarrow{a_n}\) (represented as one‐dimensional integer values) which may change over time. You need to answer two types of queries:

1. For a given range \([l,r]\), compute the sum of dot products:

[ S_1 = \sum\limits_{i=l}^{r-1} \sum\limits_{j=i+1}^{r} \overrightarrow{a_i} \cdot \overrightarrow{a_j} = \frac{\Big(\sum_{i=l}^{r} a_i\Big)^2 - \sum_{i=l}^{r}a_i^2}{2} ]

1. For the same range \([l,r]\), compute the sum of pairwise bitwise XORs:

   [ S_2 = \sum\limits_{i=l}^{r-1} \sum\limits_{j=i+1}^{r} \bigl(a_i\oplus a_j\bigr) ]

   </p>

There is also an update operation because the vectors change over time. Thus, you need to support the following three types of operations:

• Type 1: 1 l r – output \(S_1\) over the range [l, r].
• Type 2: 2 l r – output \(S_2\) over the range [l, r].
• Type 3: 3 pos val – update the vector at position pos to the new value val.

Note: All indices are 1-indexed.

inputFormat

The first line contains two integers n and m - the number of vectors and the number of operations.

The second line contains n integers representing the initial values of the vectors.

Each of the following m lines describes an operation in one of the following formats:

• 1 l r for a Type 1 query.
• 2 l r for a Type 2 query.
• 3 pos val for a Type 3 (update) query.

outputFormat

For each query of Type 1 or Type 2, output the corresponding result on a separate line.

sample

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

11
28
169
22