FIICode 2025 Qualifying Round - Elevi | Iggy and Bits

Task

Iggy the martian absolutely loves bitwise operations, and to celebrate his love for them he has prepared the following challenge for you:

He has given you his favorite integer array $[a_1, a_2, a_3,\ldots, a_n]$, after which he commanded you to perform $q$ tasks. A task can be one of the following:

1. Replacement operation. Given $p$ and $x$, Iggy wants you to replace $a_p$ with $x$.
2. And operation. Given $l$, $r$, $x$, Iggy wants you to replace $a_i$ with $(a_i \& x)$ for each $i$ ($l \le i \le r$), where $\&$ denotes the bitwise AND operation.
3. Print operation. Given $l$ and $r$, tell Iggy the value of $\displaystyle \sum_{i=l}^{r} a_i$.

Input data

The first line will contain one integer, $n$ ($1 \le n \le 10^5$).
The second line will contain $n$ integers, $a_1$, $a_2$, $a_3$, ..., $a_n$ ($1 \le a_i \le 10^9$).
The third line will contain one integer, $q$ ($1 \le q \le 10^5)$.
Each of the next $q$ lines begins with a number $c$ ($c \in \{1, 2, 3\}$).
If $c = 1$, it will be followed by two integers $p$ and $x$ ($1 \le p \le n; 1 \le x \le 10^9$).
If $c = 2$, it will be followed by three integers $l$, $r$ and $x$ ($1 \le l \le r \le n; 1 \le x \le 10^9$).
If $c = 3$, it will be followed by two integers $l$ and $r$ ($1 \le l \le r \le n$).

Output data

Print the answers for the type $3$ tasks, one on each line.

Example

stdin

12
18 13 10 2 8 1 5 5 11 10 13 19 
7
3 3 4
1 6 19
2 5 12 5
1 2 4
1 9 2
3 7 12
3 2 9

stdout

12
18
29

Explanation

After the second task, the array becomes: $[18,13,10,2,8,19,5,5,11,10,13,19]$.
After the third task, the array becomes: $[18,13,10,2,0,1,5,5,1,0,5,1]$.
After the fourth task, the array becomes: $[18,4,10,2,0,1,5,5,1,0,5,1]$.
After the fifth task, the array becomes: $[18,4,10,2,0,1,5,5,2,0,5,1]$.