Problem Description

Song Zha Zha has an $1$-indexed array $A$. Li Zha Zha has $Q$ queries. Each query has two integers $L$, $R$, asking Ran Zha Zha to do the following thing: First, find all subintervals of $[L, R]$. Then calculate their XOR sum. For example:

$A = \{1, 2, 3\}$, $L = 1$, $R = 3$.

All subintervals of $[1, 3]$ are $[1, 1], [2, 2], [3, 3], [1, 2], [2, 3], [1, 3]$. Their XOR sum is $1 + 2 + 3 + (1 \oplus 2)+ (2 \oplus 3) + (1 \oplus 2 \oplus 3)$.

XOR means exclusive or (^ in C++ or Java).

Input Format

The input contains multiple test cases.

First line contains an integer $T$ $(1 \le T \le 10)$, which is the number of test cases.

In each test case:

The first line contains two integers $N$, $Q$. $(1 \le N, Q \le 100000)$. $N$ is the length of the array $A$.

Then one line contains $N$ integers indicating $A[i]$. $(1 \le i \le N, 0 \le A[i] \le 1000000)$.

Then $Q$ lines follow. Each line has two integers $L, R$, meaning that there’s a query $[L, R]$. $(1 \le L \le R \le N)$.

Output Format

For each query, print the answer mod $1000000007$.

1
3 1
1 2 3
1 3

10