For the last birthday, Oleg was presented with an ant farm and three large ants for her. The farm is a field of a.thinsp;.times..b cells. The cell with coordinate (1, 1) is in the upper left corner. Soon he noticed that moving around his enclosure, the ants leave footprints of different colors on the white sand. For several months, Oleg watched his farm and, finally, was able to strictly describe what was happening in the enclosure.
Cells come in four colors:
- white (this means that the cell is not colored by any of the ants, indicated by the number 0)
- red (this is — the color of the first ant's footprint, denoted by the number 1)
- yellow (this is — the color of the track of the second ant, indicated by the number 2)
- green (this is — the color of the trail of the third ant, indicated by the number 3)
The ant knows how to leave its mark on the cage, erase all traces from it, turn around and take a step forward. How he will change the color of the cell and where he will turn depends only on the color of the cell he is currently standing on. Let's describe one move of the ant.
If an ant stands on a white cage, then it:
- paints it your own color
- rotates 90° to the right and takes a step forward
If the ant is not standing on a white cage, then it:
- erases the trace from it (that is, paints the cell white)
- rotates 90º to the left and takes a step forward
If an ant encounters a farm boundary in its path, it does not take a step forward.
Every minute, all three ants take turns making one move, with the first moving first, then the second, then the third.
In the morning, leaving for school, Oleg cleans the enclosure so that at the initial moment of time the sand on the entire farm is white (that is, there are no marks on it). However, the movements of the ants are so interesting that the boy cannot study normally, but instead thinks about his pets. Sitting in class, he tries to figure out what pattern he will see when he gets home. Before leaving for school, he writes down the coordinates of all his pets. Oleg knows that he will be home exactly in T minutes. In order for Oleg not to be distracted by thinking about ants during class, write a program that will reproduce the drawing that will turn out on the sand of the enclosure in T minutes.
Input
The first line contains 3 numbers a, b, T (1 ≤ a ≤ 100, 1 ≤ b ≤ 100, 1 ≤ T ≤ 10
3) — the height of the enclosure, the width of the enclosure and the time that Oleg will be away from home, respectively. The next three lines describe the position of the ants. Each line contains 2 numbers i, j (1 ≤ i ≤ a, 1 ≤ j ≤ b) — coordinates of ants (first the row number is written, and then the column number), and the first of the lines contains the coordinates of the first ant, the second — second, and in the third — third. It is guaranteed that initially there were no two ants in the same cell. Initially, all ants look up.
Imprint
Print the state of the field at time T: a lines with b numbers each separated by a space. Each number indicates the color of the footprint left in that cell of the enclosure.