F. Odd Queries on Odd Arraytime limit per test10 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output An array $$$b$$$ of length $$$m$$$ is cute if there do not exist four indices $$$1\le i < j < k < 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]$$$. InputEach 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$$$.OutputFor each test case, output $$$q$$$ integers representing the answers to each query.ExampleInput311 41 1 2 2 3 3 3 2 2 1 17 105 118 62 86 21 3 2 3 4 31 61 43 63 3 31 11 23 12 22 33 3Output4 5 4 0 10 6 3 0 3 3 0 3 NoteIn 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$$$.