Гра "Спотворення"
Павло вигадав нову гру з матрицею цілих чисел. Він бере r x c матрицю, яка має r рядків і c стовпців, і заповнює її числами від 1 до rc, розташовуючи їх зліва направо і зверху вниз (1 знаходиться у верхньому лівому куті, а rc — у нижньому правому куті). Потім він починає переставляти числа в матриці за певними правилами, які описані нижче, і записує послідовність чисел на окремий аркуш паперу. Він називає це спотворенням матриці.
Правила перестановки визначаються картою спотворення, яка є (r - 1) x (c - 1) матрицею, що складається з літер L, R і N. Початкова 4 x 5 матриця та зразкова 3 x 4 карта спотворення для неї показані нижче.
Павло спотворює матрицю в серії ходів. На першому ході Павло бере число в першому рядку і першому стовпці (воно виділено в дужках на зображенні вище для ясності) і записує його.
Записавши число, він виконує один хід спотворення:
Павло дивиться на літеру в карті спотворення, яка відповідає позиції числа, яке він щойно записав (на першому ході це літера у верхньому лівому куті). Залежно від літери в карті спотворення, 2x2 блок матриці, у верхньому лівому куті якого знаходиться число, яке він щойно записав (виділено на зображенні вище), переставляється наступним чином:
- R — блок повертається за годинниковою стрілкою.
- L — блок повертається проти годинникової стрілки.
- N — Павло не змінює матрицю на цьому ході.
На другому ході Павло бере число в першому рядку і другому стовпці, записує його і виконує хід спотворення, і так далі. Після c - 1 ходу він завершує перший рядок і переходить до другого рядка, і так далі, рухаючись зліва направо і зверху вниз. Після (r - 1)(c - 1) ходів він записав (r - 1)(c - 1) чисел і спотворив всю матрицю, тому він починає знову у верхньому лівому куті, продовжуючи спотворювати матрицю зліва направо і зверху вниз.
Матриці нижче показують ефект перших чотирьох ходів із зразковою картою спотворення.
Наступна послідовність чисел записана за перші 4 ходи: 1 7 7 9. На 5-му ході записується число з другого рядка і першого стовпця, але матриця залишається незмінною, оскільки другий рядок і перший стовпець карти спотворення містять N. За шість ходів Павло отримує 1 7 7 9 1 8.
Дано карту спотворення та кількість ходів, які Павло робить у цій грі. Визначте, скільки разів кожне число записується Павлом. Вам потрібно надати відповідь за модулем 10^5.
Вхідні дані
Перша строка вхідного файлу містить три цілі числа — r, c, і n, де r, c (2 ≤ r, c ≤ 300) є розмірами початкової матриці, n (0 ≤ n < 10^100) є кількістю ходів, які робить Павло.
Наступні r - 1 рядків містять карту спотворення з c - 1 символами R, L або N у кожному рядку.
Вихідні дані
Запишіть у вихідний файл rc рядків з одним цілим числом у кожному рядку. На i-му рядку запишіть кількість разів, коли число i записується Павлом за модулем 10^5, поки він робить свої n ходів.