F. Нечетные запросы на нечетном массиве
ограничение по времени на тест
10 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Массив $$$b$$$ длины $$$m$$$ называется милым, если не существует четырех индексов $$$1\le i \lt j \lt k \lt l \le m$$$ таких, что $$$b_i\neq b_j$$$, $$$b_i = b_k$$$ и $$$b_j = b_l$$$.

Красота массива $$$b$$$ длины $$$m$$$ определяется как сумма всех различных значений, которые встречаются нечётное количество раз в массиве $$$b$$$. Формально, пусть $$$\operatorname{cnt}(b, x)$$$ обозначает количество раз, которое значение $$$x$$$ встречается в массиве $$$b$$$. Тогда красота определяется как $$$$$$\sum\limits_{\substack{x\in \mathbb{Z}\\\operatorname{cnt}(b, x)\text{ нечетное}}}x.$$$$$$

Вам дан милый массив $$$a$$$ длины $$$n$$$, и вам нужно ответить на $$$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]$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$.

$$$i$$$-я из следующих $$$q$$$ строк содержит два целых числа $$$x'_i$$$ и $$$y'_i$$$ ($$$1\le x'_i, y'_i\le n$$$) — концы запрашиваемого подмассива в закодированной форме.

Пусть $$$\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$$$.

Выходные данные

Для каждого набора входных данных выведите $$$q$$$ целых чисел, представляющих ответы на запросы.

Пример
Входные данные
3
11 4
1 1 2 2 3 3 3 2 2 1 1
7 10
5 11
8 6
2 8
6 2
1 3 2 3 4 3
1 6
1 4
3 6
3 3 3
1 1
1 2
3 1
2 2
2 3
3 3
Выходные данные
4 5 4 0 
10 6 
3 0 3 3 0 3
Примечание

В первом наборе входных данных запросы следующие:

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