题目描述

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

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

1. 1 x: 删除 $S$ 的最后一个字符并将其添加到开头，执行 x 次。

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

输入格式

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

$N$ $Q$

$S$

$query_1$

$query_2$

$\vdots$

$query_Q$

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

t x

输出格式

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

样例

3 3
abc
2 2
1 1
2 2

b
a

10 8
dsuccxulnl
2 4
2 7
1 2
2 7
1 1

c
u
c
u

样例1解释

在第 1 个查询中，$S$ 是 "abc"，所以应该输出第 2 个字符 "b"。在第 2 个查询中，S 从 "abc" 变为 "cab"。在第 3 个查询中，S 是 "cab"，所以应该输出第 2 个字符 "a"。

数据范围

• $2 ≤ N ≤ 5 × 10^5, 1 ≤ Q ≤ 5 × 10^5, 1 ≤ x ≤ N, |S| = N$，$S$ 由小写英文字母组成，至少有一个格式为 2 x 的查询，$N、Q、x$ 都是整数。

来源

• AtCoder ABC258C