Collider

Interview

Time limit2sMemory limit256 MB

Summary

Move the particle at position i to position j on each exposure and report the particle type at position k for each query.

Level: Easy3 of 10
Topics: Array, Simulation
Solved: No attempts yet

Problem

Physicists study particles of three types: x, y and z. They load a row of $n$ numbered particles into a collider. During the experiment a beam is aimed at one particle. The exposed particle disappears from position $i$ of the row and instantly reappears at position $j$ . When it disappears, the numbers of the particles to its right drop by 1. When it reappears, the numbers of the particles to the right of the new place rise by 1. After some exposures the scientists want to know which particle sits at position $k$ . Write a program that answers them.

Input

The first line contains two integers, the number of particles $n$ and the combined number of exposures and queries $m$ ( $1 \le n \le 1000000$ , $1 \le m \le 15000$ ).

The second line contains a string of length $n$ built from the characters x, y and z.

Each of the next $m$ lines describes one exposure or one query. A line describing an exposure starts with the character a and a space, followed by two integers from the range $[1, n]$ . The first integer is the start position of the exposed particle and the second is its finish position. A line describing a query starts with the character q and a space, followed by one integer from the range $[1, n]$ , the position the scientists ask about.

Output

Print one line for every query, in the order the queries appear in the input. Line $i$ holds the answer to query $i$ , the name of the particle at that position: x, y or z.

Note

An exposure a $i$ $j$ happens in two steps. First the particle at position $i$ leaves the row, which then holds $n - 1$ particles. Then that particle is put back so that it occupies exactly position $j$ in the row of $n$ particles that results. If $i$ equals $j$ , the row does not change. For example, if the row is xyzz and the exposure is a 1 3, taking x out leaves yzz, and putting it back gives yzxz.

Examples6

Example 1

Input

15 6
xzxyyzxxzxyyzyx
a 2 10
a 15 4
q 3
a 12 2
q 14
q 2

Expected output

y
z
y

Example 2
Input
```
1 4
z
q 1
a 1 1
q 1
q 1
```
Expected output
```
z
z
z
```

Example 3

Input

5 8
xyzxy
a 1 5
q 5
q 1
a 5 1
q 1
q 5
a 3 3
q 3

Expected output

x
y
x
y
z

Example 4

Input

6 6
xyzzyx
q 1
q 2
q 3
q 4
q 5
q 6

Expected output

x
y
z
z
y
x

Example 5

Input

8 5
yyyyyyyy
a 1 8
q 1
a 8 1
q 8
q 4

Expected output

y
y
y

Example 6

Input

7 10
xyzxyzx
a 2 1
q 1
q 2
a 1 2
q 1
q 2
a 7 6
q 6
q 7
q 1

Expected output

y
x
x
y
x
z
x