Ivo has an $N\times N$ table. The table has the integers $1$ through $N^2$ 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.

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.

Input Specification

The first line contains two integers $N$ $(2\le N\le 10000)$ and $K$ $(1\le K\le 1000)$, the table dimension and the number of moves.

Each of the following $K$ lines contains three integers $X$ $(1\le X\le N^2)$, $R$ and $C$ $(1\le R,C\le N)$, the description of one move Ivo wants to make. Ivo does the moves in the order in which they are given.

Output Specification

Output $K$ 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