暂无测试数据。

蒜头君一不小心发现了大海尽头的宝藏，宝藏存在一座岛上，并排列成一条直线。

宝藏由一个长度为 $n$ 序列表示，第 $i(1\leq i\leq n)$ 个位置的价值为 $a_i$，蒜头君最开始在船上，也就是 $0$ 号位置。

接下来有 $Q$ 次操作，共有三种操作，用整数 $op$ 表示操作类型：

• op = 1：输入 x 1/2，表示蒜头君向左或者向右移动 $x$ 步，并捡起路过位置的宝藏。其中 $1$ 表示向左，$2$ 表示向右；每个位置的宝藏只能被拾取一次（比如第一次路过位置 $i$，则拾取其中的价值 $a_i$，后面再路过则不可拾取，即获得的价值为 $0$）。若移动距离超过边界，则到边界停止，边界分别为 $1$ 和 $n$。比如说当前蒜头君在 $3$，那么向左移动 $5$ 步，则最终会停留 $1$ 位置。
• op = 2：表示询问上一次移动拾取了多少价值总额，如果前面没有移动过，则输出 $0$。
• op = 3：表示询问当前蒜头君的位置在哪里。

数据保证第一步移动会让蒜头君进入 $1\sim n$，即第一步移动会让蒜头君登岛。

输入格式

输入共 $n+Q+2$ 行。

第一行输入一个正整数 $n$，表示序列的长度。

第二行输入 $n$ 个正整数 $a_i$，表示第 $i$ 个位置的价值。

接下来输入一个正整数 $Q$，表示有 $Q$ 次操作。

接下来 $Q$ 行，输入正整数 $op$；

• 如果 $op=1$，再输入 x f，其中 $f = 1$ 或 $f = 2$。
• 如果 $op = 2$，表示操作 $2$；
• 如果 $op = 3$，表示操作 $3$；

输出格式

对于每一次询问（操作 $2$、操作 $3$），输出对应答案。

数据范围

对于 $10\%$ 的数据，有 $1\leq n,q\leq 100,1\leq a_i\leq 100$。

对于另外 $20\%$ 的数据，有 $1\leq n,q\leq 10^3,1\leq a_i\leq 10^3$。

对于另外 $20\%$ 的数据，有 $1\leq n,q\leq 10^3,1\leq a_i\leq 10^9$。

对于 $100\%$ 的数据，有 $1\leq n,q\leq 10^5,1\leq a_i\leq 10^9, 1\leq x \leq n$。

由于输入数据过多，建议使用 scanf/printf。

5
1 2 3 4 5
5
1 1 2
2
1 1 2
2
3

1
2
2

5
1 2 3 4 5
5
1 3 2
2
1 1 1
2
3

6
0
2