Гра "Спотворення"#527
Павло вигадав нову гру з цілою матрицею. Він бере матрицю розміру r \times c з рядками та стовпцями, заповнюючи її числами від до зліва направо і згори вниз ( у верхньому лівому куті, у нижньому правому). Потім він починає переставляти числа в матриці за описаними нижче правилами, записуючи послідовність чисел на окремий аркуш паперу. Він називає це спотворенням матриці.
Правила перестановки визначаються картою спотворення — це матриця розміру (r - 1) \times (c - 1) з літер L, R і N. Нижче наведено приклади початкової матриці 4 \times 5 і карти спотворення 3 \times 4.
Павло спотворює матрицю послідовністю кроків. У першому кроці Павло бере число з першого рядка і першого стовпця (воно зазначено в дужках вище для наочності) і записує його.
Після запису числа він виконує спотворюючий хід:
Павло дивиться на літеру в карті спотворення, яка відповідає позиції щойно записаного числа (на першому ході — це літера у верхньому лівому куті карти). Залежно від літери у карті спотворення, 2\times2 блок матриці, у верхньому лівому куті якого міститься щойно записане число (виділено вище), переставляється таким чином:
- R — блок повертається за годинниковою стрілкою. - L — блок повертається проти годинникової стрілки. - N — Павло не змінює матрицю на цьому ході.
На другому ході Павло бере число із першого рядка і другого стовпця, записує його і виконує спотворення, і так далі. Після c-1 ходів він завершує перший рядок і переходить до другого, продовжуючи зліва направо і згори вниз. Після (r - 1)(c - 1) ходів він записує (r - 1)(c - 1) чисел і повністю проходить карту спотворення, тому починає знову з верхнього лівого кута, продовжуючи спотворювати матрицю зліва направо і згори вниз.
Нижче показано, як змінюється матриця після перших чотирьох ходів із використанням прикладової карти спотворення.
Послідовність чисел, записаних за перші ходи: . На -му ході записується число з другого рядка і першого стовпця, але матриця залишається незмінною, оскільки для цієї позиції на карті спотворення стоїть N. За шість ходів Павло отримує 1~7~7~9~1~8.
Вам задано карту спотворення та кількість ходів, які Павло робить у грі. Визначте, скільки разів кожне число було записане Павлом. Виведіть відповідь по модулю 10^5.
Перший рядок містить три цілі числа , та , де , (2 \leq r, c \leq 300) — розміри початкової матриці, а (0 \leq n < 10^{100}) — кількість ходів, які робить Павло.
Наступні r-1 рядків містять карту спотворення, де кожен містить c-1 літер R, L або N.
Виведіть рядків, у кожному з яких одне ціле число. -ий рядок повинен містити кількість разів, коли число було записано Павлом по модулю 10^5 за ходів.
Приклад 1