想象你正拿着一个 $n \times n \times n$ 的立方体，它被分割成 $n^3$ 个标号从 $1$ 到 $n^3$ 的小立方体。坐标轴的方向定义为：$x$ 轴从左到右，$y$ 轴从后到前，$z$ 轴从下到上。例如，一个 $2 \times 2 \times 2$ 的立方体标号如下：

底层 ($z = 1$): 1 2 3 4

顶层 ($z = 2$): 5 6 7 8

在 $2 \times 2 \times 2$ 的立方体中： 立方体 1 位于 $(1, 1, 1)$。 立方体 2 位于 $(2, 1, 1)$。 立方体 3 位于 $(1, 2, 1)$。 立方体 5 位于 $(1, 1, 2)$。

每次你沿着 $x, y, z$ 轴之一在切片 $k$ 处旋转立方体时，你是在沿着相应的轴旋转第 $k+1$ 层以及该轴正方向上 $k$ 之后的所有层。

图 1：在 $z = 1$ 切片处旋转后的 $2 \times 2 \times 2$ 立方体。

输入格式

第一行包含两个整数 $n$ ($2 \le n \le 1000$) 和 $m$ ($1 \le m \le 2000$)，分别表示立方体的大小和操作次数。

接下来的 $m$ 行，每行包含一个操作信息，格式为以下之一：

• x, $\theta$, $k$：将第 $k+1$ 层到第 $n$ 层绕 $x$ 轴逆时针旋转 $\theta$ 度。
• y, $\theta$, $k$：将第 $k+1$ 层到第 $n$ 层绕 $y$ 轴逆时针旋转 $\theta$ 度。
• z, $\theta$, $k$：将第 $k+1$ 层到第 $n$ 层绕 $z$ 轴逆时针旋转 $\theta$ 度。
• q $x$ $y$ $z$：这是一个查询操作。输出位于位置 $(x, y, z)$ 的立方体编号。

对于前三种操作，保证 $0 \le k \le n - 1$ 且 $\theta \in \{90, 180, 270, 360\}$。对于查询操作，$(x, y, z)$ 表示查询位置，且 $1 \le x, y, z \le n$。保证至少有一个查询操作。立方体在操作之间不会重置，即旋转是累积的。

输出格式

对于每个查询操作，输出位于给定位置的立方体编号。

样例

样例输入 1

2 8
x 360 1
y 360 1
q 1 1 2
z 90 1
x 360 1
q 1 2 1
q 2 1 1
q 2 2 2

样例输出 1

5
3
2
7

样例输入 2

2 7
x 180 1
q 1 1 1
q 1 1 2
y 270 1
q 2 1 1
q 2 1 2
q 2 2 1

样例输出 2

1
5
8
4
2

样例输入 3

3 7
y 270 1
q 1 1 1
q 1 2 3
z 360 2
q 3 2 1
q 2 2 2
q 3 3 3

样例输出 3

1
4
24
14
25