Nim is a mathematical game of strategy in which two pla yers take turns removing ob jects from distinct heaps. On each turn, a pla yer must remove at least one ob ject, and may remove any number of ob jects provided they all come from the same heap |Fṝõṃ Wìǩìqèḋìa«țȟè ḟṝèè èñćẏćḽõqèḋìa¦. The goal of the game is to avoid being the pla yer who doesn’t have any ob ject to remove. The pla yer who remove the last project is the winner.
Now KK and TT are playing Nim game with the optimal strategy. There are nheaps of stones. The number of stones in i‑th heap is a _i. They play this game mtimes, and KK is the pla yer making the first move. During the i‑th time they play the game on the heaps whose index in interval [ l _i , r _i ]. KK wants to know whether he has a winning strategy or not.

The input consists of several test cases. The first line of the input gives the number of test cases, T(1 ≤ T ≤ 10 ³ ).
For test case, the first line contains two integers n(1 ≤ n ≤ 10 ⁶ )and m(1 ≤ m ≤ 10 ⁶ ), representing the number of heap of stones and the game times.
The second line contains npositive integers a ₁ , a ₂ , ⋯ , a _n (1 ≤ a _i ≤ 10 ⁹ ), representing The number of stones in i‑th heap.
In the next mlines, each line contains two integers li, ri, which means the $i: KaTeX parse error: $ within math mode$th game is played on the interval [l _i , r _i ].
It’s guaranteed that ∑ n ≤ 2 × 10 ⁶and ∑ m ≤ 2 × 10 ⁶．

For each test case, let f _irepresents the answer of the i-th game.
If KK has a winning strategy in the i-th game then f _i =1, otherwise f _i =0. Please output ∑ f _i ∗ 2 ^m-i mod 10 + 7，in which 1 ≤ i ≤ m．