Problem Description

zxa had a great interest in exclusive disjunction(i.e. XOR) recently, therefore he took out a non-negative integer sequence $a_1,a_2,\cdots,a_n$ of length $n$.

zxa thought only doing this was too boring, hence a function $funct(x,y)$ defined by him, in which $a_x$ would be changed into $y$ irrevocably and then compute $\otimes_{1\leq i < j\leq n}{(a_i+a_j)}$ as return value.

zxa is interested to know, assuming that he called such function $m$ times for this sequence, then what is the return value for each calling, can you help him?

tips:$\otimes_{1\leq i < j\leq n}{(a_i+a_j)}$ means that $(a_1+a_2)\otimes(a_1+a_3)\otimes\cdots\otimes(a_1+a_n)\otimes(a_2+a_3)\otimes(a_2+a_4)\otimes\cdots\otimes(a_2+a_n)\otimes\cdots\otimes(a_{n-1}+a_n)$.

Input

The first line contains an positive integer $T$, represents there are $T$ test cases.

For each test case:

The first line contains two positive integers $n$ and $m$.

The second line contains $n$ non-negative integers, represent $a_1,a_2,\cdots,a_n$.

The next $m$ lines, the $i$-th line contains two non-negative integers $x$ and $y$, represent the $i$-th called function is $funct(x,y)$.

There is a blank between each integer with no other extra space in one line.

$1\leq T\leq 1000,2\leq n\leq 2\cdot10^4,1\leq m\leq 2\cdot10^4,0\leq a_i,y\leq 10^9,1\leq x\leq n,1\leq\sum{n},\sum{m}\leq10^5$

Output

For each test case, output in $m$ lines, the $i$-th line a positive integer, repersents the return value for the $i$-th called function.

1
3 3
1 2 3
1 4
2 5
3 6

4
6
8

Hint

After the first called function, this sequence is $\{4,2,3\}$, and $(4+2)\otimes(4+3)\otimes(2+3)=4$.

After the second called function, this sequence is $\{4,5,3\}$ and $(4+5)\otimes(4+3)\otimes(5+3)=6$.

After the third called function, this sequence is $\{4,5,6\}$ and $(4+5)\otimes(4+6)\otimes(5+6)=8$.