An array $$$b$$$ of length $$$m$$$ is cute if there do not exist four indices $$$1\le i \lt j \lt k \lt l \le m$$$ such that $$$b_i\neq b_j$$$, $$$b_i = b_k$$$ and $$$b_j = b_l$$$.

The beauty of an array $$$b$$$ of length $$$m$$$ is defined as the sum of all distinct values that appear an odd number of times in array $$$b$$$. Formally, let $$$\operatorname{cnt}(b, x)$$$ denote the number of times the value $$$x$$$ appears in array $$$b$$$. Then, the beauty is given by $$$$$$\sum\limits_{\substack{x\in \mathbb{Z}\\\operatorname{cnt}(b, x)\text{ is odd}}}x.$$$$$$

You are given a cute array $$$a$$$ of length $$$n$$$, and you need to answer $$$q$$$ queries online. Each query consists of two integers $$$l$$$ and $$$r$$$ ($$$1\le l\le r\le n$$$), and you must compute the beauty of the subarray $$$a_{l\ldots r}$$$$$$^{\text{∗}}$$$. Note that the queries are encoded; each subsequent query can only be decoded after calculating the answer to the preceding query.

$$$^{\text{∗}}$$$The subarray $$$a_{l \ldots r}$$$ refers to the contiguous segment of the array $$$a$$$ that starts at index $$$l$$$ and ends at index $$$r$$$, i.e., $$$[a_l, a_{l+1}, \ldots, a_r]$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1\le n, q\le 5\cdot 10^5$$$) — the length of array $$$a$$$ and the number of queries.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le n$$$) — the elements of the cute array $$$a$$$.

The $$$i$$$-th of the next $$$q$$$ lines contains two integers $$$x'_i$$$ and $$$y'_i$$$ ($$$1\le x'_i, y'_i\le n$$$) — the endpoints of the queried subarray in an encoded form.

Let $$$\text{ans}_i$$$ be the answer to the $$$i$$$-th query, with $$$\text{ans}_0 = 0$$$. Then, we calculate $$$x_i = ((x'_i - 1 + \text{ans}_{i - 1}) \bmod n) + 1$$$ and $$$y_i = ((y'_i - 1 + \text{ans}_{i - 1}) \bmod n) + 1$$$. The endpoints of the $$$i$$$-th queried subarray, $$$l_i$$$ and $$$r_i$$$, are decoded as $$$l_i = \min(x_i, y_i)$$$ and $$$r_i = \max(x_i, y_i)$$$.

It is guaranteed that the given array $$$a$$$ satisfies the conditions of a cute array.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases does not exceed $$$5\cdot 10^5$$$.

Output

For each test case, output $$$q$$$ integers representing the answers to each query.

Note

In the first test case, the queries are as follows:

$$$$$$x_1 = ((7 - 1 + 0) \bmod 11) + 1 = 7, \quad y_1 = ((10 - 1 + 0) \bmod 11) + 1 = 10$$$$$$
$$$$$$l_1 = \min(7, 10) = 7, \quad r_1 = \max(7, 10) = 10$$$$$$
Thus, the queried subarray is $$$a_{7\ldots 10} = [3, 2, 2, 1]$$$. Values $$$3$$$ and $$$1$$$ appear once (odd), and value $$$2$$$ appears twice (even). Hence, the beauty is $$$3 + 1 = 4$$$.
$$$$$$x_2 = ((5 - 1 + 4) \bmod 11) + 1 = 9, \quad y_2 = ((11 - 1 + 4) \bmod 11) + 1 = 4$$$$$$
$$$$$$l_2 = \min(9, 4) = 4, \quad r_2 = \max(9, 4) = 9$$$$$$
Thus, the queried subarray is $$$a_{4\ldots 9} = [2, 3, 3, 3, 2, 2]$$$. Values $$$2$$$ and $$$3$$$ appear three times (odd). Hence, the beauty is $$$2 + 3 = 5$$$.
$$$$$$x_3 = ((8 - 1 + 5) \bmod 11) + 1 = 2, \quad y_3 = ((6 - 1 + 5) \bmod 11) + 1 = 11$$$$$$
$$$$$$l_3 = \min(2, 11) = 2, \quad r_3 = \max(2, 11) = 11$$$$$$
Thus, the queried subarray is $$$a_{2\ldots 11} = [1, 2, 2, 3, 3, 3, 2, 2, 1, 1]$$$. Values $$$1$$$ and $$$3$$$ appear three times (odd), and value $$$2$$$ appears four times (even). Hence, the beauty is $$$1 + 3 = 4$$$.
$$$$$$x_4 = ((2 - 1 + 4) \bmod 11) + 1 = 6, \quad y_4 = ((8 - 1 + 4) \bmod 11) + 1 = 1$$$$$$
$$$$$$l_4 = \min(6, 1) = 1, \quad r_4 = \max(6, 1) = 6$$$$$$
Thus, the queried subarray is $$$a_{1\ldots 6} = [1, 1, 2, 2, 3, 3]$$$. Values $$$1$$$, $$$2$$$, and $$$3$$$ each appear twice (even). Hence, the beauty is $$$0$$$.

In the second test case, the queries are as follows:

$$$$$$x_1 = ((1 - 1 + 0) \bmod 6) + 1 = 1, \quad y_1 = ((6 - 1 + 0) \bmod 6) + 1 = 6$$$$$$
$$$$$$l_1 = \min(1, 6) = 1, \quad r_1 = \max(1, 6) = 6$$$$$$
Thus, the queried subarray is $$$a_{1\ldots 6} = [1, 3, 2, 3, 4, 3]$$$. Values $$$1$$$, $$$2$$$, and $$$4$$$ appear once (odd), and value $$$3$$$ appears three times (odd). Hence, the beauty is $$$1 + 2 + 3 + 4 = 10$$$.
$$$$$$x_2 = ((1 - 1 + 10) \bmod 6) + 1 = 5, \quad y_2 = ((4 - 1 + 10) \bmod 6) + 1 = 2$$$$$$
$$$$$$l_2 = \min(5, 2) = 2, \quad r_2 = \max(5, 2) = 5$$$$$$
Thus, the queried subarray is $$$a_{2\ldots 5} = [3, 2, 3, 4]$$$. Values $$$2$$$ and $$$4$$$ appear once (odd), and value $$$3$$$ appears twice (even). Hence, the beauty is $$$2 + 4 = 6$$$.

In the third test case, all elements of array $$$a$$$ are equal to $$$3$$$.

For any subarray of odd length, the value $$$3$$$ appears an odd number of times, so the beauty is $$$3$$$.
For any subarray of even length, the value $$$3$$$ appears an even number of times, so the beauty is $$$0$$$.

Odd Queries on Odd Array

Examples