题目描述

I 君最近学习了加法，他的老师把他带到一块很长的黑板前，依次进行了 $q$ 次操作，分为如下四种：

• 1 x，将正整数 $x$ 写在黑板最右边。
• 2 x，设最左边的数为 $s$，求 $\lfloor\dfrac{s}{10^x}\rfloor$ 除以 $10$ 的余数。
• 3，将黑板最左边两个数擦掉，然后把这两个数的和写在黑板最左边。保证原来黑板上至少有两个数。
• 4，在黑板最右边抄写一遍最左边的数字，然后擦去最左边的数字。

作为 I 君的好朋友，你能在老师询问他时，帮助 I 君求出答案吗？

输入格式

输入的第一行有一个正整数 $q$，表示老师的操作数。

之后 $q$ 行，每行一或两个整数，格式同题目描述，表示一次操作。保证第一次操作是 1 操作。

输出格式

对于每一个 2 操作，你都要输出一行一个整数。

样例 #1

样例输入 #1

10
1 3492387402394872347320423954235423402398234324324498374876543210
1 19
2 4
1 4
4
3
2 1
2 2
4
2 6

样例输出 #1

4
2
0
6

样例 #2, #3, #4, #5

点我下载大样例

样例 $2\sim 5$ 分别满足测试点 $1,7,10,12$ 的限制。

提示

【数据规模】

设 $l$ 为 1 操作中的最大数字位数，$s$ 为所有 1 操作的数字位数和。

对于全部数据，$1\le q\le 10^5$，$1\le l\le 10^6$，$1\le s\le 2\times 10^6$，2 操作的 $x$ 不超过 $10^6+1$。

【提示】

使用 swap 函数交换两个 STL 容器（除 array 外），时间复杂度为常数。