Physicists are conducting an experiment to study particles of three types: x, y and z. They launch a numbered row of n particles into the collider. During the experiment, one specific particle is affected, after which the particle disappears from the i-th place of the row and instantly appears at the place j. After it disappears, the numbers of particles to the right decrease by 1, and after the appearance, the numbers of particles to the right increase by 1. After a certain number of impacts, physicists are interested in which particle is in place k. Write a program to help physicists.
Input
The first line of the file contains two integers: n – number of particles and m — total number of exposures and questions (1 ≤ n ≤ 1000000, 1 ≤ m ≤ 15000). On the second line — a sequence of characters x, y and z of length n. Each of the next m lines (1 ≤ m ≤ 15000) describes an impact or question. The line, which describes the impact, begins with the character a and after the space two integers from the interval [1; n]. The first of them shows the initial, and the second - the final location of the particle during the impact. The line in which the question is described begins with the symbol q and after a space one integer from the interval [1; n]. It indicates the position that physicists are interested in.
Imprint
Output as many lines as there are questions in the input file. In line number i you need to write the answer to the question i — the name of the corresponding particle x, y or z.
Explanations for example
The sequence after the first exposure – xxyyzxxzxzyyzyx, the sequence after the second exposure – xxyxyzxxzxzyyzy, sequence after the third exposure –
Examples
| # |
Input |
Output |
| 1 |
15 6
xzxyyzxxzxyyzyx
a 2 10
a 15 4
q 3
a 12 2
q 14
q2 |
y
z
y |