G. Hola
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It's finals time in university and Gustavo has been worried about his modern art appreciation exams.

Of course this is not like any other modern art appreciation class, this class uses advanced programs to evaluate the paintings, and give the correct interpretation of them instead of this false idea that museums seek to sell, saying that there is an open interpretation for modern art (false of course).

The final exam consist of developing a faster algorithm to retrieve the correct interpretation of a painting.

To main algorithm is too hard to explain in this brief problem description, but an important part of the exam is to reflect the picture in several axes, and then reevaluate its interpretation, just to be sure that even changing its point of view it will always give the same interpretation.

Tomorrow is due date and Gustavo is almost done with the exam, he already implemented the main algorithm to interpret pictures, but he is also getting sleepy and still needs to implement a code to reflect the picture correctly, but he is already too tired to do it.

So you like a good friend are here to help him.

There will be 5 different queries that you need to respond:

  • r a: reflect the picture by axe a
  • r b: reflect the picture by axe b
  • r c: reflect the picture by axe c
  • r d: reflect the picture by axe d
  • q x y: id of pixel in position (x, y)

The initial id's of the pixels are in order from left to right, and then from top to bottom.

The evaluated paintings are always a perfect square for this exam.

Input

In the first line there will be two integers n $$$(1 \leq n \leq 10^9)$$$, q $$$(1 \leq q \leq 10^5)$$$, the size of the painting and the number of queries respectively.

In the next q lines, there will be one query, it will correspond to one of the query types listed before.

Output

For each query of type (q x y), print a line with the current index of the pixel in that position. Where $$$'x'$$$ is the number of the row from top to bottom and $$$'y'$$$ is the number of the column from left to right.

Example
Input
4 3
q 2 3
r a
q 2 3
Output
7
10