旋转

题目描述

给你正整数 $N$ 和 $Q$,以及一个长度为 $N$ 的由小写英文字母组成的字符串 $S$。

处理 $Q$ 个查询。每个查询是以下两种类型之一。

1 x:连续执行以下操作 $x$ 次:删除 $S$ 的最后一个字符,并将其添加到开头。

2 x:输出 $S$ 的第 $x$ 个字符。

输入格式

输入按以下格式从标准输入给出:

N Q
S
query_1
query_2
⋮
query_Q

每个查询的格式如下,其中 $t$ 为 $1$ 或 $2$:

t x

输出格式

对于每个格式为 2 x 的查询,在一行中输出答案。

样例

3 3
abc
2 2
1 1
2 2

b
a

在第 1 个查询中,$S$ 为 abc,因此应输出第 2 个字符 b。 在第 2 个查询中,$S$ 从 abc 变为 cab。 在第 3 个查询中,$S$ 为 cab,因此应输出第 2 个字符 a。

10 8
dsuccxulnl
2 4
2 7
1 2
2 7
1 1
1 2
1 3
2 5

c
u
c
u

数据范围

• $2 \le N \le 5 \times 10^5$
• $1 \le Q \le 5 \times 10^5$
• $1 \le x \le N$
• $|S|=N$
• $S$ 由小写英文字母组成。
• 至少存在一个格式为 2 x 的查询。
• $N$, $Q$, $x$ 均为整数。