Magic Cube

Imagine you are holding an $n \times n \times n$ cube, which is split into $n^3$ smaller cubes labeled from 1 to $n^3$. The axes run left to right for the $x$-axis, back to front for the $y$-axis, and bottom to top for the $z$-axis. For example, a $2 \times 2 \times 2$ cube is labeled as follows.

Bottom layer ($z=1$):

1 2 
3 4

Top layer ($z=2$):

5 6 
7 8

In this $2 \times 2 \times 2$ cube, cube 1 is at (1, 1, 1), cube 2 is at (2, 1, 1), cube 3 is at (1, 2, 1), and cube 5 is at (1, 1, 2).

Each time you rotate the cube at slice $k$ around one of the $x$-, $y$-, or $z$-axes, the $(k+1)$th layer and all layers after $k$ in that axis's increasing direction rotate along with it.

The first line contains two integers $n$ ($2 \leq n \leq 1\,000$) and $m$ ($1 \leq m \leq 2\,000$), the size of the cube and the number of operations.

Each of the next $m$ lines describes one operation in one of the following forms.

• x, $\theta$, $k$: Rotate slices $k+1$ through $n$ by $\theta$ degrees counterclockwise around the $x$-axis.
• y, $\theta$, $k$: Rotate slices $k+1$ through $n$ by $\theta$ degrees counterclockwise around the $y$-axis.
• z, $\theta$, $k$: Rotate slices $k+1$ through $n$ by $\theta$ degrees counterclockwise around the $z$-axis.
• q x y z: Query. Output the cube at location $(x, y, z)$.

For the first three operations, $0 \leq k \leq n-1$ and $\theta \in \{90, 180, 270, 360\}$ are guaranteed. For queries, $(x, y, z)$ is the location, with $1 \leq x, y, z \leq n$. At least one query is guaranteed. The cube is not reset between operations, so rotations accumulate.

For each query operation, output the number of the cube at the given location, one per line.