Problem:


Matrix Operation

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 N \times N 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:

 WR r c v  (Write operation) write a integer v into the cell (r,c) (1 \leq v \leq 1,000,000)
 CP r1 c1 r2 c2  (Copy operation) copy a character in the cell (r1,c1) into the cell (r2,c2)
 SR r1 r2  (Swap Row operation) swap the r1-th row and r2-th row
 SC c1 c2  (Swap Column operation) swap the c1-th column and c2-th column
 RL  (Rotate Left operation) rotate the whole matrix in counter-clockwise direction by 90 degrees
 RR  (Rotate Right operation) rotate the whole matrix in clockwise direction by 90 degrees
 RH  (Reflect Horizontal operation) reverse the order of the rows
 RV  (Reflect Vertical operation) reverse the order of the columns

Input

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 (1 \leq N,Q \leq 40,000).
Next three integers, A B, and C, are coefficients to calculate values in initial matrix (1 \leq A,B,C \leq 1,000,000),
and they are used as follows: A_{r,c} = (r * A + c * B) mod C where r and c are row and column indices, respectively (1\leq r,c\leq N).
Last four integers, D, E, F, and G, are coefficients to compute the final hash value mentioned in the next section (1 \leq D \leq E \leq N, 1 \leq F \leq G \leq N, E - D \leq 1,000, G - F \leq 1,000).
Each of next Q lines contains one operation in the format as described above.

Output

Output a hash value h computed from the final matrix B by using following pseudo source code.

h <- 314159265
for r = D...E
  for c = F...G
    h <- (31 * h + B_{r,c}) mod 1,000,000,007

where "<-" is a destructive assignment operator, "for i = S...T" indicates a loop for i from S to T (both inclusive), and "mod" is a remainder operation.

Sample Input 1

2 1 3 6 12 1 2 1 2
WR 1 1 1

Output for the Sample Input 1

676573821

Sample Input 2

2 1 3 6 12 1 2 1 2
RL

Output for the Sample Input 2

676636559

Sample Input 3

2 1 3 6 12 1 2 1 2
RH

Output for the Sample Input 3

676547189

Sample Input 4

39989 6 999983 999979 999961 1 1000 1 1000
SR 1 39989
SC 1 39989
RL
RH
RR
RV

Output for the Sample Input 4

458797120



Sample input:
2 1 3 6 12 1 2 1 2
WR 1 1 1


Sample output:
676573821

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    N, Q, A, B, C, D, E, F, G = map(int, readline().split())
    d = 0; rx = 0; ry = 0
    *X, = range(N)
    *Y, = range(N)
    def fc(d, x, y):
        if d == 0:
            return x, y
        if d == 1:
            return y, N-1-x
        if d == 2:
            return N-1-x, N-1-y
        return N-1-y, x
    mp = {}
    for i in range(Q):
        c, *g = readline().strip().split()
        c0, c1 = c
        if c0 == "R":
            if c1 == "L":
                d = (d - 1) % 4
            elif c1 == "R":
                d = (d + 1) % 4
            elif c1 == "H":
                if d & 1:
                    rx ^= 1
                else:
                    ry ^= 1
            else: #c1 == "V":
                if d & 1:
                    ry ^= 1
                else:
                    rx ^= 1
        elif c0 == "S":
            a, b = map(int, g); a -= 1; b -= 1
            if c1 == "R":
                if d & 1:
                    if rx != ((d & 2) > 0):
                        a = N-1-a; b = N-1-b
                    X[a], X[b] = X[b], X[a]
                else:
                    if ry != ((d & 2) > 0):
                        a = N-1-a; b = N-1-b
                    Y[a], Y[b] = Y[b], Y[a]
            else: #c1 == "C":
                if d & 1:
                    if ((d & 2) == 0) != ry:
                        a = N-1-a; b = N-1-b
                    Y[a], Y[b] = Y[b], Y[a]
                else:
                    if ((d & 2) > 0) != rx:
                        a = N-1-a; b = N-1-b
                    X[a], X[b] = X[b], X[a]
        elif c0 == "C": #c == "CP":
            y1, x1, y2, x2 = map(int, g); x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
            x1, y1 = fc(d, x1, y1)
            x2, y2 = fc(d, x2, y2)
            if rx:
                x1 = N-1-x1; x2 = N-1-x2
            if ry:
                y1 = N-1-y1; y2 = N-1-y2
            key1 = (X[x1], Y[y1]); key2 = (X[x2], Y[y2])
            if key1 not in mp:
                xa, ya = key1
                mp[key2] = (ya*A + xa*B + A + B) % C
            else:
                mp[key2] = mp[key1]
        else: #c == "WR":
            y, x, v = map(int, g); x -= 1; y -= 1
            x, y = fc(d, x, y)
            if rx:
                x = N-1-x
            if ry:
                y = N-1-y
            key = (X[x], Y[y])
            mp[key] = v
    MOD = 10**9 + 7
    h = 314159265
    for y in range(D-1, E):
        for x in range(F-1, G):
            x0, y0 = fc(d, x, y)
            if rx:
                x0 = N-1-x0
            if ry:
                y0 = N-1-y0
            x0 = X[x0]; y0 = Y[y0]
            key = (x0, y0)
            if key in mp:
                v = mp[key]
            else:
                v = ((y0+1)*A + (x0+1)*B) % C
            h = (31 * h + v) % MOD
    write("%d\n" % h)
solve()