By Aleksandar Ivanović Serbia
You are given an array a of N elements. Array a is 0-indexed. There are two types of queries that you should perform on the array.
INVERT i j k: Invert the K^{th} bit on each element in the range [a_{i},a_{j}]
Σ i j: Output the sum of the elements in the range [a_{i},a_{j}].
Note that 0^{th} bit is the least significant bit and 31^{st} bit is the most significant bit.
The first line contains one integer N–size of the array. Second line contains N integers that are initial values of the elements in the array. Third line contains one integer Q–number of the queries. Following Q lines contain one query per line.
Output contains \(\begin{matrix} \sum ¿\\ Q¿\\ \end{matrix}\) lines, where \(\begin{matrix} \sum ¿\\ Q¿\\ \end{matrix}\) represents the number of \(\sum¿\) queries, and each line contains the answer to the corresponding query.
Input Sample | Output Sample |
4 1 2 3 1 5 SUM 0 2 INVERT 0 2 0 SUM 0 2 INVERT 3 3 10 SUM 3 3 |
6 5 1025 |