该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

徐老师最近在思考一个问题，我们学过如此多的数据结构

但是这些数据结构里很少出现 撤销 这个操作，也就是回滚某些步骤

一旦涉及到这个操作，数据结构的难度往往就会几何级上升

现在徐老师想实现一个动态队列，这个队列的操作一共有三种：

1. 1 x 表示在队列末尾添加一个元素 $x$
2. 2 x 表示撤销之前的 $x$ 次操作（仅针对 $1$ 和 $2$ 操作）
3. 3 x 表示查询现在队列中第 $x$ 个元素值（该操作不会被撤销）

例如徐老师依次进行以下操作: 一开始队列为空

1. 1 5，操作后队列为 $[5]$
2. 1 6，操作后队列为 $[5,6]$
3. 1 3，操作后队列为 $[5,6,3]$
4. 2 1，撤销一次操作，即撤销第 $3$ 次操作，操作后队列为 $[5,6]$
5. 1 7，操作后队列为 $[5,6,7]$
6. 3 1，查询结果为 $5$
7. 2 2，撤销两次操作，即撤销第 $4,5$ 次操作，操作后队列为 $[5,6,3]$
8. 3 2，查询结果为 $6$
9. 2 1，撤销一次操作，即撤销第 $7$ 次操作，操作后队列为 $[5,6,7]$
10. 3 3，查询结果为 $7$

输入格式

输入一行包含一个整数 $n$，表示操作次数

接下来 $n$ 行，每行包含两个整数 $A,B$，请使用以下方式计算真正的 $op$ 和 $x$

其中 $op$ 表示本次操作的操作编号，$x$ 表示本次操作的操作数，$Lastans$ 表示上一次询问的答案，若之前没有出现过询问，则 $Lastans = 0$

op = (Lastans * 229 + A * 239) % 3 + 1;
x = (Lastans * 251 + B * 269) % 100000;

输出格式

对于每次查询输出结果

数据范围

对于 $20\%$ 的数据满足：$n \leq 200$。

对于另外 $50\%$ 的数据满足：不包含 $2$ 操作

对于 $100\%$ 的数据 $n, x, A,B\leq 100000$，且保证操作合法

样例输入1

10
42 69145
8469 2974
6336 1487
6503 33829
9171 36803
5725 33829
1480 12263
9360 12263
6965 87355
4465 55013

样例输出1

5
6
7

样例解释1

实际的操作就是题目中给出的例子

10
1 5
1 6
1 3
2 1
1 7
3 1
2 2
3 2
2 1
3 3