Devendra loves the XOR operation very much which is denoted by $\land\operatorname$ sign in most of the programming languages. He has a list $\mbox{A}$ of $N$ numbers and he wants to know the answers of $\mbox{M}$ queries. Each query will be denoted by three numbers i.e. $K,P,R$ .

For query $K,P\ \text{and}\ R$, he has to print the value of the $\textit{KPRsum}$ which can be described as given below. As the value of the $\textit{KPRsum}$ can be large. So, print it modulus $(10^9+7)$.

$KPRsum=\sum_{i=P}^{R-1}\sum_{j=i+1}^R\left(K\oplus\left(A[i]\oplus A[j]\right)\right)$

Input Format

The first line contains an integer $N$, i.e., the number of the elements in the list. List is numbered from $\mbox{1}$ to $N$.

Next line will contain $N$ space seperated integers.

Third line will contain a number $\mbox{M}$ i.e. number of queries followed by $\mbox{M}$ lines each containing integers $K,P\&R$.

Output Format

Print $\mbox{M}$ lines, $i^{\mbox{th}}$ line will be answer of $i^{\mbox{th}}$ query. Answer will be 0 in case of P=R.

Constraints

$1\leq N\leq10^5$

$1\leq A[i]\leq10^6$

$1\leq M\leq10^5$

$0\leq K\leq10^6$

$1\leq P\leq R\leq N$

Sample Input

3
1 2 3
2
1 1 3
2 1 3

Sample Output

5
4

Explanation

For first query, it will will be $(1\oplus(1\oplus2))+(1\oplus(1\oplus3))+(1\oplus(2\oplus3))=5$

见题面

见题面