TABLIC - Tablica
English | Vietnamese |
Ivo has an N×N table. The table has the integers 1 through N2 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 X to cell (R, C) and proceeds as follows:
- While X is not in column C, rotate the row it is in.
- While X is not in row R, rotate the column it is in.
Ivo wants to move K numbers one after another. Write a program that calculates the number of rotations needed.
Input
The first line contains two integers N (2 ≤ N ≤ 10 000) and K (1 ≤ K ≤ 1000), the table dimension and the number of moves.
Each of the following K lines contains three integers X (1 ≤ X ≤ N2), R and C (1 ≤ R, C ≤ N), the description of one move Ivo wants to make. Ivo does the moves in the order in which they are given.
Output
Output K lines; for each move, output the number of rotations needed.
Example
Input 4 1 6 3 4 Output 3
Input 4 2 6 3 4 6 2 2 Output 3 5
Input 5 3 1 2 2 2 2 2 12 5 5 Output 2 5 3
Added by: | Race with time |
Date: | 2009-02-17 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | COCI 2008/2009 - Croatian Regional |