displaylzy recently like to study the copying and querying of strings, he found that after the string is copied, the change of position will have a certain pattern now he would like to ask you to solve the queries about the position of the string after copying.

Specifically, a string of length $n$ with $m$ operations will be given.

There are two kinds of operations.

$(1, x, len, y):$ Starting from the $x$-th position of the string, take $len$ length of the string and then clone this substring $y$ times.

By cloning, each letter will be repeated $y$ times.

For example,

for abaab with $n=5$, the operation $(1,1,2,3)$ is applied,

i.e. $(ab)aab$ becomes $(aaabbb)aab$

$(2, x):$ Query the $x$-th character of the current string.

The input contains $2 + m$ lines.

The first line contains two integers, $n$ and $m$, $(n,m \le 10^5)$, denoting the length of the initial string and the number of operations.

The second line contains a string $s$ of length $n$, denoting the initial string.

The next $m$ lines, each line denotes an operation.

It is guaranteed that all operations are legal. The length of the string after at each time will not exceed $10^{18}$.

For all queries like $(2, x)$, output the character in the corresponding position at that time.