给你一个最初为空的数组。您需要执行给定格式的 $$$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'$$$。要在第 $$$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)$$$,
$$$\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$$$),描述一个操作。
输出
对于每个查询,打印一个整数 - 该查询的答案。
示例
输入 #1
5 0 0 0 1 0 1 0 5 5 2 1 0 5 2 1 0 2 4 3 3
输出 #1
1 1 2 6 3
输入 #2
5 2 0 0 2 2 0 1 1 0 0 2 0 3 2 2 0 0 2 3 0
输出 #2
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$$$