#abc258c. [abc258_c]Rotation

[abc258_c]Rotation

Problem Statement

You are given positive integers NN and QQ, and a string SS of length NN consisting of lowercase English letters.

Process QQ queries. Each query is of one of the following two types.

  • 1 x: Perform the following xx times in a row: delete the last character of SS and append it to the beginning.
  • 2 x: Print the xx-th character of SS.

Constraints

  • 2leNle5times1052 \\le N \\le 5 \\times 10^5
  • 1leQle5times1051 \\le Q \\le 5 \\times 10^5
  • 1lexleN1 \\le x \\le N
  • S=N|S|=N
  • SS consists of lowercase English letters.
  • At least one query in the format 2 x.
  • NN, QQ, xx are all integers.

Input

Input is given from Standard Input in the following format:

NN QQ SS mathrmquery1\\mathrm{query}_1 mathrmquery2\\mathrm{query}_2 vdots\\vdots mathrmqueryQ\\mathrm{query}_Q

Each query is in the following format, where tt is 11 or 22:

tt xx

Output

For each query in the format 2 x, print the answer in a single line.


Sample Input 1

3 3
abc
2 2
1 1
2 2

Sample Output 1

b
a

In the 11-st query, SS is abc, so the 22-nd character b should be printed. In the 22-nd query, SS is changed from abc to cab. In the 33-rd query, SS is cab, so the 22-nd character a should be printed.


Sample Input 2

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

Sample Output 2

c
u
c
u