H. Holy Diver
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив, изначально он пустой. Вам нужно выполнить $$$n$$$ операций следующего вида:

  • «$$$a$$$ $$$l$$$ $$$r$$$ $$$k$$$»: дописать $$$a$$$ в конец текущего массива, а затем подсчитать число пар целых чисел $$$x, y$$$ таких, что $$$l \leq x \leq y \leq r$$$ и $$$\operatorname{mex}(a_{x}, a_{x+1}, \ldots, a_{y}) = k$$$.

Элементы массива пронумерованы с $$$1$$$ в том порядке, в котором они добавляются в массив.

Чтобы сделать эту задачу более идейной, мы не будем сообщать вам реальные параметры запросов. Вместо этого вам будут даны целые числа $$$a'$$$, $$$l'$$$, $$$r'$$$, $$$k'$$$. Чтобы получить $$$a$$$, $$$l$$$, $$$r$$$, $$$k$$$ на $$$i$$$-й операции, вам нужно выполнить следующие действия:

  • $$$a := (a' + lans) \bmod(n + 1)$$$,
  • $$$l := (l' + lans) \bmod{i} + 1$$$,
  • $$$r := (r' + lans) \bmod{i} + 1$$$,
  • если $$$l > r$$$, то поменять местами $$$l$$$ и $$$r$$$,
  • $$$k := (k' + lans) \bmod(n + 1)$$$,
где $$$lans$$$ — ответ на предыдущую операцию, изначально $$$lans$$$ равен нулю. $$$i$$$ — номер операции, операции нумеруются с $$$1$$$.

$$$\operatorname{mex}(S)$$$, где $$$S$$$ это мультимножество целых неотрицательных чисел, есть наименьшее неотрицательное целое число, не входящее в это множество. Например, $$$\operatorname{mex}(\{2, 2, 3\}) = 0$$$, а $$$\operatorname{mex} (\{0, 1, 4, 1, 6\}) = 2$$$.

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — количество запросов.

Следующие $$$n$$$ строк содержат описания запросов.

Каждая из этих $$$n$$$ строк содержит четыре целых неотрицательных целых числа $$$a'$$$, $$$l'$$$, $$$r'$$$, $$$k'$$$ ($$$0, \leq a', l', r', k' \leq 10^9$$$).

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

Для каждого запроса выведите единственное число — ответ на запрос.

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

Для первого теста из условия расшифрованные значения $$$a$$$, $$$l$$$, $$$r$$$, $$$k$$$ следующие:

$$$a_1=0,l_1=1,r_1=1,k_1=1$$$

$$$a_2=1,l_2=1,r_2=2,k_2=0$$$

$$$a_3=0,l_3=1,r_3=3,k_3=1$$$

$$$a_4=1,l_4=1,r_4=4,k_4=2$$$

$$$a_5=2,l_5=1,r_5=5,k_5=3$$$

Для второго теста из условия расшифрованные значения $$$a$$$, $$$l$$$, $$$r$$$, $$$k$$$ следующие:

$$$a_1=2,l_1=1,r_1=1,k_1=2$$$

$$$a_2=2,l_2=1,r_2=2,k_2=1$$$

$$$a_3=0,l_3=1,r_3=3,k_3=0$$$

$$$a_4=0,l_4=2,r_4=2,k_4=3$$$

$$$a_5=0,l_5=3,r_5=4,k_5=0$$$