配点 : $300$ 点

問題文

正整数 $N,Q$ と、長さ $N$ の英小文字からなる文字列 $S$ が与えられます。

以下で説明されるクエリを $Q$ 個処理してください。クエリは次の $2$ 種類のいずれかです。

• 1 x: 「$S$ の末尾の文字を削除し、先頭に挿入する」という操作を $x$ 回連続で行う。
• 2 x: $S$ の $x$ 番目の文字を出力する。

制約

• $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 の形式のクエリが $1$ 個以上与えられる。
• $N,Q,x$ はすべて整数。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $Q$

$S$

$\mathrm{query}_1$

$\mathrm{query}_2$

$\vdots$

$\mathrm{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