Memory limit: 256 MiB
Time limit: 1000 ms
Input file: stdin
Output file: stdout
Problem type: traditional
Judging mode: text compare
Alice has a pixel stamper of $N$ x $N$ pixels, and she has a $N$ x $N$ pixel grid. A pixel on the stamper is described with a value $A$$i,j$.
A pixel on the pixel grid is described with value $B$$i,j$, which is initially $0$.
There are a total of $Q$ events, happening in chronological order:
1. L-rotate: Alice left rotates her stamper (i.e. pixel $A$$i,j$ is now pixel $A$$N+1-j,i$, for all $1 \le i,j \le N$)
2. R-rotate: Alice right rotates her stamper (i.e. pixel $A$$i,j$ is now pixel $A$$j,N+1-i$, for all $1 \le i,j \le N$)
3. Stamp: Stamp the pixel stamper on the grid (i.e. add $A$$i,j$ to $B$$i,j$, for all $1 \le i,j \le N$)
4. Query x y: Find the value of $B$$x,y$ ($1 \le x, y \le N$)
Help Alice to perform the operations!
The first line contain two integers $N$ and $Q$.
The following $N$ lines each contains $N$ integers, representing the values in the pixel stamper. For line $i+1$, the $N$ integers represent $A$$i,1$ to $A$$i,N$ respectively.
The following Q lines contains an operation, either L-rotate, R-rotate, Stamp or Query x y.
For each Query x y operation, output the value of $B$$x,y$ in a single line.
For all test data,
$1 \le N \le 1000$
$1 \le Q \le 10^5$
$1 \le A$$i,j$ $\le 10^6$
| Subtask |
Score |
Additional Constraints |
| $1$ |
$11$ |
There are Stamp and Query operations only |
| $2$ |
$17$ |
$1 \le N,Q \le 300$ |
| $3$ |
$23$ |
Stamp operation happens once and only once |
| $4$ |
$24$ |
All Query operations happens after Stamp operations |
| $5$ |
$25$ |
No additional Constraints |