Queries on anti-xor
Recently our coach - Etibar has invented a new bitwise operation. It is like a reverse of xor operation. Then called it as anti-xor. Now he is giving you a new problem which is related to his invention on queries. The sign of anti-xor is #.
You are given N number. Perform the following operations on those integers.
1) Anti-xor X with integer from L to R. This query is represented as “1 L R X”
2) Output the sum of all numbers from L to R. This query is represented as “2 L R”
Assume that all numbers are 20 bits integers. So you do anti-xor operation on last 20 bits.
Input
You are given an integer N (1 ≤ N ≤ 100000). In the second line you are given N integers (0 ≤ A_i ≤ 10^6). The next line contains the number of queries Q (1 ≤ Q ≤ 100000). Each of the next Q lines contains one query of one of the forms above.
Output
For each query of the type “2 L R” print on a separate line the sum of all integers from L to R.