Операція з матрицею#3287

Операція з матрицею

2 секунди

64 мегабайти

Дуже складна

Ви студент, який шукає роботу. Сьогодні ви проходили іспит на працевлаштування до ІТ‑компанії. Вам запропонували написати ефективну програму для виконання низки операцій над квадратною матрицею.

Спочатку вам надано матрицю $N \times N$ N \times N. Далі йде серія з $Q$ операцій. Усі операції, окрім останньої, змінюють матрицю. Після всіх операцій потрібно вивести хеш‑значення, обчислене за результатуючою матрицею, як описано нижче.

Доступні операції:

WR r c v (Запис): Записати ціле число $v$ у комірку $(r, c)$ , тобто встановити $A_{r, c} = v$ A_{r, c}=v. ( $1 \leq v \leq 1000000$ 1 \le v \le 1\,000\,000)
CP $r_{1}$ r_1 $c_{1}$ c_1 $r_{2}$ r_2 $c_{2}$ c_2 (Копіювати): Скопіювати значення з комірки $(r_{1}, c_{1})$ (r_1, c_1) у комірку $(r_{2}, c_{2})$ (r_2, c_2)
SR $r_{1}$ r_1 $r_{2}$ r_2 (Обмін рядків): Поміняти місцями рядки $r_{1}$ r_1 і $r_{2}$ r_2
SC $c_{1}$ c_1 $c_{2}$ c_2 (Обмін стовпців): Поміняти місцями стовпці $c_{1}$ c_1 і $c_{2}$ c_2
RL (Поворот вліво): Повернути всю матрицю на $9 0^{\circ}$ 90^\circ проти годинникової стрілки
RR (Поворот вправо): Повернути всю матрицю на $9 0^{\circ}$ 90^\circ за годинниковою стрілкою
RH (Горизонтальне відображення): Змінити порядок рядків на зворотний
RV (Вертикальне відображення): Змінити порядок стовпців на зворотний

Вхідні дані

Перший рядок кожного тесту містить дев'ять цілих чисел: $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 — початкове значення матриці в позиції $(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

Далі йдуть $Q$ рядків, кожний з яких описує одну операцію в зазначеному форматі.

Вихідні дані

Виведіть ціле хеш‑значення $h$ , обчислене за остаточною матрицею $B$ за таким алгоритмом:

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

де <- означає присвоєння, for i = S ... T — цикл для $i$ від $S$ до $T$ включно, а mod — операція взяття залишку.

Приклади

Приклад 1