問題文

正整数 $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 の形式の各クエリについて、答えを一行に出力せよ。

入力例 1

3 3
abc
2 2
1 1
2 2

出力例 1

b
a

$1$ 個目のクエリのとき、$S$ は abc なので $2$ 文字目の b を出力します。 $2$ 個目のクエリのとき、$S$ は abc から cab に変わります。 $3$ 個目のクエリのとき、$S$ は cab なので $2$ 文字目の a を出力します。

入力例 2

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

出力例 2

c
u
c
u