CF1148H.Holy Diver

You are given an array which is initially empty. You need to perform $n$ operations of the given format:

• "$a$ $l$ $r$ $k$": append $a$ to the end of the array. After that count the number of integer pairs $x, y$ such that $l \leq x \leq y \leq r$ and $\operatorname{mex}(a_{x}, a_{x+1}, \ldots, a_{y}) = k$.

The elements of the array are numerated from $1$ in the order they are added to the array.

To make this problem more tricky we don't say your real parameters of the queries. Instead your are given $a'$, $l'$, $r'$, $k'$. To get $a$, $l$, $r$, $k$ on the $i$-th operation you need to perform the following:

• $a := (a' + lans) \bmod(n + 1)$,
• $l := (l' + lans) \bmod{i} + 1$,
• $r := (r' + lans) \bmod{i} + 1$,
• if $l \gt r$ swap $l$ and $r$,
• $k := (k' + lans) \bmod(n + 1)$,

where $lans$ is the answer to the previous operation, initially $lans$ is equal to zero. $i$ is the id of the operation, operations are numbered from $1$.

The $\operatorname{mex}(S)$, where $S$ is a multiset of non-negative integers, is the smallest non-negative integer which does not appear in the set. For example, $\operatorname{mex}({2, 2, 3}) = 0$ and $\operatorname{mex} ({0, 1, 4, 1, 6}) = 2$.

你将获得一个初始为空的数组。你需要执行 $n$ 次如下格式的操作：

• “$a$ $l$ $r$ $k$”：将 $a$ 追加到数组末尾；随后统计满足 $l \leq x \leq y \leq r$ 且 $\operatorname{mex}(a_{x}, a_{x+1}, \ldots, a_{y}) = k$ 的整数对 $(x, y)$ 的个数。

数组元素从 $1$ 开始编号，编号顺序即其被加入数组的顺序。

为使本题更具挑战性，我们不直接给出查询的真实参数，而是提供 $a'$、$l'$、$r'$、$k'$。对于第 $i$ 次操作，需按如下方式计算真实参数 $a$、$l$、$r$、$k$：

• $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 = 0$；$i$ 表示当前操作的编号，操作编号从 $1$ 开始。

$\operatorname{mex}(S)$ 表示非负整数多重集 $S$ 的最小未出现非负整数（minimum excluded value）。例如，$\operatorname{mex}(\{2, 2, 3\}) = 0$，而 $\operatorname{mex}(\{0, 1, 4, 1, 6\}) = 2$。

The first line contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of the array.

The next $n$ lines contain the description of queries.

Each of them $n$ lines contains four non-negative integers $a'$, $l'$, $r'$, $k'$ ($0, \leq a', l', r', k' \leq 10^9$), describing one operation.

第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）—— 数组的长度。

接下来的 $n$ 行描述了查询操作。

每行包含四个非负整数 $a'$、$l'$、$r'$、$k'$（$0 \leq a', l', r', k' \leq 10^9$），描述一次操作。

For each query print a single integer — the answer to this query.

对于每个查询，输出一个整数——该查询的答案。

For the first example the decoded values of $a$, $l$, $r$, $k$ are the following:

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

For the second example the decoded values of $a$, $l$, $r$, $k$ are the following:

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

第一个样例中，$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$