Ваня занимается работой с большими данными. Его проект занимается обработкой гигантских таблиц статистических данных. Ваня отвечает за разработку модуля преобразования таблиц, который выполняет перестановку строк, столбцов и ячеек таблицы.
Модуль занимается обработкой таблицы, состоящей из \(h\) строк и \(w\) столбцов, строки пронумерованы сверху вниз от \(0\) до \(h−1\), столбцы пронумерованы слева направо от \(0\) до \(w −1\). Ячейка в \(i\)-й
строке, \(j\)-м столбце таблицы обозначается как \([i, j]\). Исходно ячейка \([i, j]\) содержит число \(i \times w + j\).
На рис. 1. приведен пример исходного заполнения таблицы для \(h = 3,\ w = 5\).
Модуль преобразования таблиц может выполнять следующие три типа операций.
На рис. 2. показано, как выглядит приведенная выше таблица после выполнения последовательности операций «c 0 1», «r 0 1», «f 0 0 1 2».
После выполнения всех операций Ваня вычисляет контрольную сумму для таблицы: сумма по
всем ячейкам \([i, j]\) значений \((v[i][j] \times 17^i \times 19^j
)\) mod (\(10^9 + 7\)).Здесь \(v[i][j]\) означает значение в ячейке
[i, j], а операция « mod » означает операцию взятия остатка. Например, контрольная сумма для таблицы из примера вычисляется следующим образом: \((6 \times 17^0 \times 19^0+ 2 \times 17^0 \times 19^1+ \dots +14 \times 17^2 \times 19^4
) \ mod\
(10^9 + 7) = 564 830 737\).
Помогите Ване выполнить все операции и вычислить контрольную сумму таблицы, которая
получится в итоге.
Поскольку входные данные для этой задачи слишком велики, чтобы задавать их непосредственно, для ввода вам потребуется процедура расширения массива. Эта процедура не имеет специфических особенностей, которые надо использовать в решении задачи, предполагаемое жюри решение
этой задачи в явном виде генерирует все массивы и далее работает с ними так же, как если бы оно
считало их из входных данных.
Опишем процедуру генерации массива длины \(n\) по массиву длины \(2 \le k \le n\). Пусть
задан массив целых неотрицательных чисел \(A\) = (\(a[1]\), \(a[2]\), \(\dots\), \(a[k]\)).
Массив целых чисел
\(Ax \ = \ (ax[1], \ ax[2], \dots, \ ax[n])\) будем называть расширением массива \(A\) по модулю \(r\) до размера \(n\),
если его элементы вычисляются по следующим формулам.
- Если \(1 \le i \le k\), то \(ax[i] \ = \ a[i]\).
- Если \(k + 1 \le i \le n\), то \(ax[i] \ = \ (10007 \times ax[i − 2] + 10009 \times ax[i − 1] + 87277) \ mod \ r\).
Здесь как «mod» также обозначена операция взятия остатка по модулю \(r\).
Например, выполним расширение массива \(A\) = (1, 4, 3) до 5 элементов по модулю 13
\(ax[1] \ = \ a[1] \ = \ 1\).
\(ax[2] \ = \ a[2] \ = \ 4.\)
\(ax[3] \ = \ a[3] \ = \ 3.\)
\(ax[4] \ = \ (10007 \times ax[2] + 10009 \times ax[3] + 87277) \ mod \ 13 = 157332 \ mod \ 13 = 6.\)
\(ax[5] \ = \ (10007 \times ax[3] + 10009 \times ax[4] + 87277) \ mod \ 13 = 177352 \ mod \ 13 = 6.\)
Таким образом, \(Ax \ = \ (1, 4, 3, 6, 6)\).
Входные данные
Первая строка ввода содержит числа \(h\), \(w\), \(n\) — размеры таблицы и число преобразований, которые необходимо выполнить (\(1 \le h, w \le 5 000,\) \(2 \le n \le 10^6\)
).
Вторая строка содержит строку \(s\) длины \(n\) — последовательность типов преобразований,
\(s[i]\) = «c» задает операцию обмена столбцов, \(s[i]\) = «r» — операцию обмена строк, \(s[i]\) = «f» —
операцию обмена ячеек.
Следующие четыре строки задают массивы \(A\), \(B\), \(C\), \(D\), соответственно. Каждый массив задается
числом \(k, 2 \le k \le n, k \le 1000\), после чего следует \(k\) чисел — элементы массива. Элементы массивов
\(A\) и \(C\) удовлетворяют ограничению \(0 \le a[i], c[i] \le h − 1\), элементы массивов \(B\) и \(D\) удовлетворяют
ограничению \(0 \le b[i], d[i] \le w − 1\).
Пусть \(Ax\) является расширением массива \(A\) по модулю \(h\) до размера \(n\), массив \(Bx\) является
расширением массива \(B\) по модулю \(w\) до размера \(n\), массив \(Cx\) является расширением массива \(C\)
по модулю \(h\) до размера \(n\) и массив \(Dx\) является расширением массива \(D\) по модулю \(w\) до размера
n.
Операции, которые требуется выполнить с таблицей, определяются следующим образом: тип \(i\)-й
операции задается символом \(s[i]\), а параметры получаются из массивов \(Ax\), \(Bx\), \(C\)x, \(Dx\).
- Если \(s[i]\) = «c», то \(i\)-я операция «c Bx[i] Dx[i]»;
- Если \(s[i]\) = «r», то \(i\)-я операция «r Ax[i] Cx[i]»;
- Если \(s[i]\) = «f», то \(i\)-я операция «f Ax[i] Bx[i] Cx[i] Dx[i]»;
