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$$$.