Matrix Operation#3287

Matrix Operation

2 seconds

64 megabytes

Very hard

You are a student looking for a job. Today, you took an employment examination at an IT company. You were asked to write an efficient program to perform several operations on a square matrix.

Initially, you are given an $N \times N$ N \times N matrix. Then you are given a series of $Q$ operations. All operations except the last modify the matrix. After all operations, you must output a hash value computed from the resulting matrix as described below.

The available operations are:

WR r c v (Write): Write integer $v$ into cell $(r, c)$ , i.e. set $A_{r, c} = v$ A_{r, c}=v. ( $1 \leq v \leq 1, 000, 000$ 1 \le v \le 1,000,000)
CP $r_{1}$ r_1 $c_{1}$ c_1 $r_{2}$ r_2 $c_{2}$ c_2 (Copy): Copy the value in cell $(r_{1}, c_{1})$ (r_1, c_1) to cell $(r_{2}, c_{2})$ (r_2, c_2)
SR $r_{1}$ r_1 $r_{2}$ r_2 (Swap Rows): Swap rows $r_{1}$ r_1 and $r_{2}$ r_2
SC $c_{1}$ c_1 $c_{2}$ c_2 (Swap Columns): Swap columns $c_{1}$ c_1 and $c_{2}$ c_2
RL (Rotate Left): Rotate the entire matrix $9 0^{\circ}$ 90^\circ counterclockwise
RR (Rotate Right): Rotate the entire matrix $9 0^{\circ}$ 90^\circ clockwise
RH (Reflect Horizontal): Reverse the order of the rows
RV (Reflect Vertical): Reverse the order of the columns

Input

The first line of each test case contains nine integers: $N$ , $Q$ , $A$ , $B$ , $C$ , $D$ , $E$ , $F$ , $G$ .

$1 \leq N, Q \leq 40000$ 1 \le N, Q \le 40\,000
$1 \leq A, B, C \leq 1000000$ 1 \le A, B, C \le 1\,000\,000
$1 \leq r, c \leq N$ 1 \le r, c \le N
$A_{r, c} = (r \times A + c \times B) mod C$ A_{r,c} = (r \times A + c \times B) \bmod C is the initial matrix value at position $(r, c)$
$1 \leq D \leq E \leq N$ 1 \le D \le E \le N, $1 \leq F \leq G \leq N$ 1 \le F \le G \le N, $E - D \leq 1000$ E-D \le 1\,000, $G - F \leq 1000$ G-F \le 1\,000

Next, $Q$ lines follow, each describing an operation in the format above.

Output

Output the integer hash value $h$ computed from the final matrix $B$ using the following algorithm:

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

where <- indicates assignment, for i = S ... T means a loop for $i$ from $S$ to $T$ (inclusive), and mod is the remainder operation.

Examples

Example 1