На прошлый день рождения Олегу подарили муравьиную ферму и трех больших муравьев для нее. Ферма представляет собой поле размером a × b клеток. Клетка с координатой (1, 1) находится в левом верхнем углу. Вскоре он заметил, что передвигаясь по своему вольеру, муравьи оставляют на белом песке следы разных цветов. На протяжении нескольких месяцев Олег наблюдал за своей фермой и, наконец, смог строго описать происходящее в вольере.
Клетки бывают четырех цветов:
- белая (это значит, что клетка не покрашена ни одним из муравьев, обозначается цифрой 0)
- красная (это — цвет следа первого муравья, обозначается цифрой 1)
- желтая (это — цвет следа второго муравья, обозначается цифрой 2)
- зеленая (это — цвет следа третьего муравья, обозначается цифрой 3)
Муравей умеет оставлять на клетке свой след, стирать с нее все следы, поворачиваться и делать шаг вперед. То, как он изменит цвет клетки и куда он повернется, зависит только от цвета клетки, на которой он сейчас стоит. Опишем один ход муравья.
Если муравей стоит на белой клетке, то он:
- красит ее в свой цвет
- поворачивается на 90° вправо и делает шаг вперед
Если же муравей стоит не на белой клетке, то он:
- стирает с нее след (то есть красит клетку в белый цвет)
- поворачивается на 90º влево и делает шаг вперед
Если на пути муравья встречается граница фермы, шаг вперед он не делает.
Каждую минуту все три муравья по очереди делают один ход, причем сначала ходит первый, потом второй, потом третий.
Утром, уходя в школу, Олег чистит вольер так, что в начальный момент времени песок на всей ферме белый (то есть на нем нет никаких следов). Однако перемещения муравьев такие интересные, что мальчик не может нормально учиться, а вместо этого думает о своих любимцах. Сидя на занятиях, он старается понять, какой узор он увидит, когда вернется домой. Перед тем, как уйти на учебу, он записывает координаты всех своих питомцев. Олегу известно, что дома он будет ровно через T минут. Для того, чтобы Олег не отвлекался во время занятий на размышления о муравьях, напишите программу, которая сама воспроизведет рисунок, который получится на песке вольера через T минут.
Входные данные
В первой строке вводятся 3 числа a, b, T (1 ≤ a ≤ 100, 1 ≤ b ≤ 100, 1 ≤ T ≤ 10
3) — высота вольера, ширина вольера и время, которое Олега не будет дома, соответственно. Следующие три строки содержат описание положения муравьев. В каждой строке записано по 2 числа i, j (1 ≤ i ≤ a, 1 ≤ j ≤ b) — координаты муравьев (сначала записан номер строки, а затем номер столбца), причем в первой из строчек записаны координаты первого муравья, во второй — второго, а в третьей — третьего. Гарантируется, что в одной и той же клетке изначально не находилось двух муравьев. Изначально все муравьи смотрят вверх.
Выходные данные
Выведите состояние поля на момент времени T: a строк по b чисел в каждой через пробел. Каждое число обозначает цвет следа, оставленного в данной клетке вольера.