Операция с матрицей

N×N

Вы студент, который ищет работу. Сегодня вы сдавали экзамен для трудоустройства в IT-компанию. Вам предложили написать эффективную программу для выполнения ряда операций. Сначала вам показали квадратную матрицу и список операций. Все операции, кроме одной, изменяют матрицу, а последняя операция выводит символ в указанной ячейке. Пожалуйста, помните, что вам нужно вывести итоговую матрицу после выполнения всех операций.

Ниже приведены подробности операций:

WR r c v (Операция записи) записывает целое число v в ячейку (r,c) (

1 ≤ v ≤ 1,000,000

) CP r1 c1 r2 c2 (Операция копирования) копирует символ из ячейки (r1, c1) в ячейку (r2, c2) SR r1 r2 (Операция обмена строк) меняет местами r1-ю строку и r2-ю строку SC c1 c2 (Операция обмена столбцов) меняет местами c1-й столбец и c2-й столбец RL (Операция поворота влево) поворачивает всю матрицу против часовой стрелки на 90 градусов RR (Операция поворота вправо) поворачивает всю матрицу по часовой стрелке на 90 градусов RH (Операция горизонтального отражения) переворачивает порядок строк RV (Операция вертикального отражения) переворачивает порядок столбцов

Входные данные

(1 ≤ N, Q ≤ 40,000)

(1 ≤ A, B, C ≤ 1,000,000)

A_{r,c}=(r*A+c*B)modC

(1 ≤ r, c ≤ N)

(1 ≤ D ≤ E ≤ N, 1 ≤ F ≤ G ≤ N, E−D ≤ 1,000, G−F ≤ 1,000)

Первая строка каждого теста содержит девять целых чисел. Первые два числа в строке, N и Q, указывают размер матрицы и количество запросов соответственно. Следующие три числа, A, B и C, являются коэффициентами для вычисления значений в начальной матрице, и они используются следующим образом: где r и c — индексы строки и столбца соответственно. Последние четыре числа, D, E, F и G, являются коэффициентами для вычисления итогового хэш-значения, упомянутого в следующем разделе. Каждая из следующих Q строк содержит одну операцию в формате, описанном выше.

Выходные данные

Выведите хэш-значение h, вычисленное из итоговой матрицы B, используя следующий псевдокод.

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

где "<-" — оператор деструктивного присваивания, "for i = S...T" обозначает цикл для i от S до T (включительно), а "mod" — операция взятия остатка.

Примеры