COCI '08 Regional #4 Tablica

View as PDF

Points: 15
Time limit: 1.0s
Memory limit: 32M

Problem type

Ivo has an table. The table has the integers through inscribed in row-major order. The following operations can be done on the table:

1. Rotate a row – all cells in a single row are rotated right, so that the number in the last column moves to the first.
2. Rotate a column – all cells in a single column are rotated down, so that the number in the last row moves to the first.

Ivo occasionally feels the urge to move a number to cell and proceeds as follows:

• While is not in column , rotate the row it is in.
• While is not in row , rotate the column it is in.

Here is an example of how to move number to cell , start from the initial configuration:

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
 1 2 3 4 8 5 6 7 9 10 11 12 13 14 15 16
 1 2 3 4 7 8 5 6 9 10 11 12 13 14 15 16
 1 2 3 16 7 8 5 4 9 10 11 6 13 14 15 12

Ivo wants to move numbers one after another. Write a program that calculates the number of rotations needed.

Input Specification

The first line contains two integers and , the table dimension and the number of moves.

Each of the following lines contains three integers , and , the description of one move Ivo wants to make. Ivo does the moves in the order in which they are given.

Output Specification

Output lines; for each move, output the number of rotations needed.

Sample Input 1

4 1
6 3 4

Sample Output 1

3

Sample Input 2

4 2
6 3 4
6 2 2

Sample Output 2

3
5

Sample Input 3

5 3
1 2 2
2 2 2
12 5 5

Sample Output 3

2
5
3