Преобразование таблицы
Преобразование таблицы
Ваня занимается работой с большими данными. Его проект занимается обработкой гигантских таблиц статистических данных. Ваня отвечает за разработку модуля преобразования таблиц, который выполняет перестановку строк, столбцов и ячеек таблицы.
Модуль занимается обработкой таблицы, состоящей из h строк и w столбцов, строки пронумерованы сверху вниз от 0 до h - 1, столбцы пронумерованы слева направо от 0 до w - 1. Ячейка в i-й строке, j-м столбце таблицы обозначается как [i, j]. Исходно ячейка [i, j] содержит число i * w + j.
На рис. 1. приведен пример исходного заполнения таблицы для h = 3, w = 5.
Модуль преобразования таблиц может выполнять следующие три типа операций.
На рис. 2. показано, как выглядит приведенная выше таблица после выполнения последовательности операций «**c 0 1**», «**r 0 1**», «**f 0 0 1 2**».
После выполнения всех операций Ваня вычисляет контрольную сумму для таблицы: сумма по всем ячейкам [i, j] значений (vij
* 17i
* 19j
) mod (109
+ 7). Здесь vij
означает значение в ячейке [i, j], а операция «mod» означает операцию взятия остатка. Например, контрольная сумма для таблицы из примера вычисляется следующим образом: (6 * 170
* 190
+ 2 * 170
* 191
+ ... + 14 * 172
* 194
) mod (109
+ 7) = 564 830 737.
Помогите Ване выполнить все операции и вычислить контрольную сумму таблицы, которая получится в итоге.
Поскольку входные данные для этой задачи слишком велики, чтобы задавать их непосредственно, для ввода вам потребуется процедура расширения массива. Эта процедура не имеет специфических особенностей, которые надо использовать в решении задачи, предполагаемое жюри решение этой задачи в явном виде генерирует все массивы и далее работает с ними так же, как если бы оно считало их из входных данных.
Опишем процедуру генерации массива длины n по массиву длины 2 ≤ k ≤ n. Пусть задан массив целых неотрицательных чисел A = (a1
, a2
, ..., ak
). Массив целых чисел Ax = (ax1
, ax2
, ..., axn
) будем называть расширением массива A по модулю r до размера n, если его элементы вычисляются по следующим формулам.
- Если 1 ≤ i ≤ k, то
axi
=ai
. - Если k + 1 ≤ i ≤ n, то
axi
= (10007 *axi-2
+ 10009 *axi-1
+ 87277) mod r.
Здесь как «mod» также обозначена операция взятия остатка по модулю r. Например, выполним расширение массива A = (1, 4, 3) до 5 элементов по модулю 13.
ax1
= a1
= 1.
ax2
= a2
= 4.
ax3
= a3
= 3.
ax4
= (10007 * ax2
+ 10009 * ax3
+ 87277) mod 13 = 157332 mod 13 = 6.
ax5
= (10007 * ax3
+ 10009 * ax4
+ 87277) mod 13 = 177352 mod 13 = 6.
Таким образом, Ax = (1, 4, 3, 6, 6).
Входные данные
Первая строка ввода содержит числа h, w, n - размеры таблицы и число преобразований, которые необходимо выполнить (1 ≤ h, w ≤ 5 000, 2 ≤ n ≤ 106
).
Вторая строка содержит строку s длины n - последовательность типов преобразований, si
= «c» задает операцию обмена столбцов, si
= «r» - операцию обмена строк, si
= «f» - операцию обмена ячеек.
Следующие четыре строки задают массивы A, B, C, D, соответственно. Каждый массив задается числом k, 2 ≤ k ≤ n, k ≤ 1000, после чего следует k чисел - элементы массива. Элементы массивов A и C удовлетворяют ограничению 0 ≤ ai
, ci
≤ h - 1, элементы массивов B и D удовлетворяют ограничению 0 ≤ bi
, di
≤ w - 1.
Пусть Ax является расширением массива A по модулю h до размера n, массив Bx является расширением массива B по модулю w до размера n, массив Cx является расширением массива C по модулю h до размера n и массив Dx является расширением массива D по модулю w до размера n.
Операции, которые требуется выполнить с таблицей, определяются следующим образом: тип i-й операции задается символом si
, а параметры получаются из массивов Ax, Bx, Cx, Dx.
- Если
si
= «c», то i-я операция «cBxi Dxi
»; - Если
si
= «r», то i-я операция «rAxi Cxi
»; - Если
si
= «f», то i-я операция «fAxi Bxi Cxi Dxi
»;
Выходные данные
Выведите одно число - контрольную сумму таблицы после выполнения всех преобразований.
3 5 3 crf 3 0 0 0 3 0 0 1 3 0 1 1 3 1 0 2
564830737