SOLVE

LATER

Xor sum

/

You are given an array $$A[]$$ of size $$N$$. Now you are given $$Q$$ queries to be performed over this array. In each query, you are given $$2$$ space separated integers $$L$$ and $$R$$. For each query, you need to you need to find the summation of the xor-sum of all triplets $$(i,j,k)$$ of the sub-array $$L...R$$ , where $$ L \le i < j < k \le R $$.

In short, you need to find $$ \sum (A[i] \oplus A[j] \oplus A[k]) $$, over all triplets $$ (i,j,k)$$ , such that $$ L \le i < j < k \le R $$ . Print the answer for each query , **Modulo** $$10^9+7$$

**Input Format**

The first line contains a single integer *$$N$$*.

The next line contains array $$A[]$$ of *$$N$$* integers.

The next line contains $$2$$ space separated integers $$Q$$ and $$2$$.

E*ach of the next $$Q$$* lines contain*s two space separated integers $$L$$ and $$R$$ *

**Output Format :**

Print *$$Q$$ lines, the $$i^{th}$$ line denoting the answer to the $$i^{th}$$ query, Modulo $$10^9+7$$*

**Input Constraints : **

\(1 \le N,Q \le 10^5 \)

\(1 \le A[i] \le 10^{12} \)

\(1 \le L \le R \le N \)

Explanation

$$ (1 \oplus 2 \oplus 3)+(2 \oplus 3 \oplus 4)+(1 \oplus 2 \oplus 4)+(1 \oplus 3 \oplus 4)=18 $$

Time Limit:
2.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...