프로그램 명: coci_tabli

제한시간: 1 초

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:

Here is an example of how to move number 6 to cell (3, 4), start from the initial configuration:

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

The first line contains two integers N (2 ≤ N ≤ 10000) 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 K lines; for each move, output the number of rotations needed.

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

출처:coci/2008-2009/regional