Problems
Matrix Operation
Matrix Operation
\textit{N}×\textit{N}
You are a student looking for a job. Today you had an employment examination for an IT company. They asked you to write an efficient program to perform several operations. First, they showed you an square matrix and a list of operations. All operations but one modify the matrix, and the last operation outputs the character in a specified cell. Please remember that you need to output the final matrix after you finish all the operations.
Followings are the detail of the operations:
\textbf{WR r c v} (Write operation) write a integer v into the cell (r,c) (
1 ≤ \textit{v }≤ 1,000,000
) \textbf{CP r1 c1 r2 c2} (Copy operation) copy a character in the cell (r1, c2) into the cell (r2, c2) \textbf{SR r1 r2 } (Swap Row operation) swap the r1-th row and r2-th row \textbf{SC c1 c2} (Swap Column operation) swap the c1-th column and c2-th column \textbf{RL} (Rotate Left operation) rotate the whole matrix in counter-clockwise direction by 90 degrees \textbf{RR} (Rotate Right operation) rotate the whole matrix in clockwise direction by 90 degrees \textbf{RH} (Reflect Horizontal operation) reverse the order of the rows \textbf{RV } (Reflect Vertical operation) reverse the order of the columns
\InputFile
(1 ≤ \textit{N}, \textit{Q }≤ 40,000)
(1 ≤ \textit{A}, \textit{B}, \textit{C }≤ 1,000,000)
\textit{A}_\{r,c\}=(\textit{r}*\textit{A}+\textit{c}*\textit{B})\textit{modC}
(1 ≤ \textit{r}, \textit{c }≤ \textit{N})
(1 ≤ \textit{D }≤ \textit{E }≤ \textit{N}, 1 ≤ \textit{F }≤ \textit{G }≤ \textit{N}, \textit{E}−\textit{D }≤ 1,000, \textit{G}−\textit{F} ≤ 1,000)
First line of each testcase contains nine integers. First two integers in the line, N and Q, indicate the size of matrix and the number of queries, respectively . Next three integers, A B, and C, are coefficients to calculate values in initial matrix , and they are used as follows: where r and c are row and column indices, respectively . Last four integers, D, E, F, and G, are coefficients to compute the final hash value mentioned in the next section . Each of next Q lines contains one operation in the format as described above.
\OutputFile
Output a hash value \textbf{h} computed from the final matrix \textbf{B} by using following pseudo source code.
\begin{verbatim}
h <- 314159265
for r = D...E
for c = F...G
h <- (31 * h + B_{r,c}) mod 100,000,007
\end{verbatim}where "\textbf{<-}" is a destructive assignment operator, "\textbf{for i = S...T}" indicates a loop for \textbf{i} from \textbf{S} to \textbf{T} (both inclusive), and "\textbf{mod}" is a remainder operation.
Input example #1
2 1 3 6 12 1 2 1 2 WR 1 1 1
Output example #1
676573821