Little Stjepan often likes to go out with his friends and have fun in a popular nightclub in Zagreb. However, Stjepan sometimes drinks too much soda and gets light headed from all the sugar. Last night was an example of this, which is why Stjepan had the same image in his mind the whole time. It was a scribble of number spirals of some sort. Since he can't quite remember what the image looked like, but can describe it, he is asking you to reconstruct it for him.
Stjepan recalls that the image was of the shape of a table consisting of numbers written in rows and columns. Also, he recalls that there were spirals in that table. For each spiral, the starting position is known, as well as the direction it's moving in, which can be clockwise and counter-clockwise. An example is shown in the images below. The spirals created Stjepan's image in exactly steps in the following way:
- Initially, the table is empty, and each spiral is in its own starting position.
- In each following step, each spiral moves to its next position. It is possible that, at times, the spirals leave the boundaries of the table, but also to return within it.
- After exactly steps, for each field in the table, the final value is the value of the earliest step in which one of the spirals touched that field.
The first line of input contains positive integers , and .
Each of the following lines contains three positive integers , , and , the starting position of the spiral and its direction ( - clockwise, - counter-clockwise). No two spirals will begin in the same field.
You must output lines with numbers, representing the table after each spiral makes steps.
In test cases worth of total points, it will hold: and and , i.e. and will be equal to the integer division of with .
Sample Input 1
3 3 1 2 2 0
Sample Output 1
9 2 3 8 1 4 7 6 5
Sample Input 2
3 3 1 2 2 1
Sample Output 2
3 2 9 4 1 8 5 6 7
Sample Input 3
3 3 2 1 1 0 1 2 0
Sample Output 3
1 1 4 6 5 5 19 18 17
Explanation for Sample Output 3
For simplicity's sake, the letter was added to the numbers from the first spiral, and the letter to the numbers from the second spiral. Only the first steps of the first spiral are shown, and steps of the second spiral. The fields in gray are the fields from the table we're interested in, all other fields are out of the table's bounds, but are shown to illustrate the way the spirals move outside of the table.