RoAlgo Contest #9 | Bit Showdown

Task

The two Runtime Terror teams met up in a fierce robot match-up, which is going to decide who is the best Runtime Terror team!

In order to quickly settle the fight, the members of the two teams decided to test these robots in a somewhat unusual event, namely summing numbers up! Now you are helping the members of the 22105 Runtime Terror team win this fight, but there is a catch -- you have to get this done fast.

Namely, you are given an array $v$ of $n$ integers and $q$ queries. In each of the $q$ queries, you will have to find the sum of the following values, depending on the type:

• $1 \ L \ R$ -- find the sum of the bitwise AND for all unordered pairs of integers in that given subarray. In other words, find $\sum_{i=L}^{R} \sum_{j=i+1}^{R} v_i \& v_j$.
• $2 \ L \ R$ -- find the sum of the bitwise XOR for all unordered pairs of integers in that given subarray. In other words, find $\sum_{i=L}^{R} \sum_{j=i+1}^{R} v_i \oplus v_j$.
• $3 \ L \ R$ -- find the sum of the bitwise OR for all unordered pairs of integers in that given subarray. In other words, find $\sum_{i=L}^{R} \sum_{j=i+1}^{R} v_i | v_j$.

Help your favorite team win the round so that they can show the world they are the best Runtime Terrors out there.

Input data

On the first line you will find $n$, the number of integers in the array. On the next line you will find the $n$ integers forming the array $v$.

On the third line you will have $q$, the number of queries. On each of the next $q$ lines you will have three integers $t \ L \ R$, where $t$ is the type of the query, $L$ and $R$ are the ends of the subarray in question.

Output data

The output will contain $q$ lines, representing the answers for each query.

Constraints and clarifications

• $1 \leq n, q \leq 5 \cdot 10^5$;
• $0 \leq v_i < 2^{20}$;
• $1 \leq t \leq 3$;
• $1 \leq L < R \leq n$;

Example

stdin

9
8 1 9 4 7 9 4 9 3
14
1 7 8
2 1 4
1 5 6
3 1 7
2 2 8
3 2 3
2 3 6
3 5 7
1 1 9
2 1 9
3 1 9
1 2 5
2 2 9
1 4 6

stdout

0
48
1
210
166
9
57
35
77
278
355
7
216
5