CF2153F.Odd Queries on Odd Array

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

长度为 $m$ 的数组 $b$ 被称为“可爱的”（cute），当且仅当不存在四个下标 $1\le i \lt j \lt k \lt l \le m$，使得 $b_i\neq b_j$，$b_i = b_k$ 且 $b_j = b_l$。

长度为 $m$ 的数组 $b$ 的“美观度”（beauty）定义为：在数组 $b$ 中出现奇数次的所有不同数值之和。形式化地，令 $\operatorname{cnt}(b, x)$ 表示数值 $x$ 在数组 $b$ 中出现的次数，则美观度为

$$\sum\limits_{\substack{x\in \mathbb{Z}\\\operatorname{cnt}(b, x)\text{ 是奇数}}}x.$$

你被给定一个长度为 $n$ 的可爱数组 $a$，并需要在线回答 $q$ 个查询。每个查询包含两个整数 $l$ 和 $r$（满足 $1\le l\le r\le n$），你需要计算子数组 $a_{l\ldots r}$$^{\text{∗}}$ 的美观度。注意：这些查询是经过编码的；每一个后续查询只有在计算出前一个查询的答案后才能解码。

$^{\text{∗}}$ 子数组 $a_{l \ldots r}$ 指的是数组 $a$ 中从下标 $l$ 开始、到下标 $r$ 结束的连续段，即 $[a_l, a_{l+1}, \ldots, a_r]$。

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

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1\le n, q\le 5\cdot 10^5$）——分别表示数组 $a$ 的长度和查询次数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1\le a_i\le n$）——即“可爱数组” $a$ 的元素。

接下来 $q$ 行中的第 $i$ 行包含两个整数 $x'_i$ 和 $y'_i$（$1\le x'_i, y'_i\le n$）——表示以编码形式给出的第 $i$ 次查询所对应的子数组端点。

设 $\text{ans}_i$ 为第 $i$ 次查询的答案，且定义 $\text{ans}_0 = 0$。然后我们计算 $x_i = ((x'_i - 1 + \text{ans}_{i - 1}) \bmod n) + 1$ 和 $y_i = ((y'_i - 1 + \text{ans}_{i - 1}) \bmod n) + 1$。第 $i$ 次查询所对应子数组的端点 $l_i$ 和 $r_i$ 通过解码得到：$l_i = \min(x_i, y_i)$，$r_i = \max(x_i, y_i)$。

保证所给数组 $a$ 满足“可爱数组”的条件。

保证所有测试用例中 $n$ 的总和与 $q$ 的总和均不超过 $5\cdot 10^5$。

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

对于每个测试用例，输出 $q$ 个整数，分别表示每个查询的答案。

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

在第一个测试用例中，查询如下：

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

  因此，所查询的子数组为 $a_{7\ldots 10} = [3, 2, 2, 1]$。其中值 $3$ 和 $1$ 各出现一次（奇数次），值 $2$ 出现两次（偶数次）。故美丽值为 $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$$

  因此，所查询的子数组为 $a_{4\ldots 9} = [2, 3, 3, 3, 2, 2]$。其中值 $2$ 和 $3$ 各出现三次（奇数次）。故美丽值为 $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$$

  因此，所查询的子数组为 $a_{2\ldots 11} = [1, 2, 2, 3, 3, 3, 2, 2, 1, 1]$。其中值 $1$ 和 $3$ 各出现三次（奇数次），值 $2$ 出现四次（偶数次）。故美丽值为 $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$$

  因此，所查询的子数组为 $a_{1\ldots 6} = [1, 1, 2, 2, 3, 3]$。其中值 $1$、$2$ 和 $3$ 各出现两次（偶数次）。故美丽值为 $0$。

在第二个测试用例中，查询如下：

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

  因此，所查询的子数组为 $a_{1\ldots 6} = [1, 3, 2, 3, 4, 3]$。其中值 $1$、$2$ 和 $4$ 各出现一次（奇数次），值 $3$ 出现三次（奇数次）。故美丽值为 $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$$

  因此，所查询的子数组为 $a_{2\ldots 5} = [3, 2, 3, 4]$。其中值 $2$ 和 $4$ 各出现一次（奇数次），值 $3$ 出现两次（偶数次）。故美丽值为 $2 + 4 = 6$。

在第三个测试用例中，数组 $a$ 的所有元素均等于 $3$。

• 对于任意长度为奇数的子数组，值 $3$ 出现奇数次，因此美丽值为 $3$。
• 对于任意长度为偶数的子数组，值 $3$ 出现偶数次，因此美丽值为 $0$。