Problem Description

Little Q has a $N \times N$ table. If $N = 4$, he fills in $1$ in the first row and first column, $2$ in the second column of the first row, $\cdots$, $5$ in the first column of the second row, $\cdots$, $15$ in the third column of the fourth row, and $16$ in the fourth column of the fourth row.

Now, Little Q performs the following operations on the table:
1. Move rows: Shift all cells in a row to the right, so that the number in the last column moves to the first column.
2. Move columns: Shift all cells in a column down, so that the number in the last row moves to the first row.

Little Q wants to move a number $X$ to cell $(R, C)$, and performs the following operations:
- When $X$ is not in the $C$th column, move the row it is in.
- When $X$ is not in the $R$th row, move the column it is in.

Below is an example of how to move the number $6$ to cell $(3, 4)$.

Little Q wants to move $K$ numbers. How many operations are needed at least?

Input Format

The first line contains two positive integers $N$ and $K$, representing the size of the table and the number of moves, respectively.

Next, $K$ lines each contain:
- Three integers $X, R, C$, as described in the problem.

Output Format

For each query, output the minimum number of moves required on a new line.

Sample Input and Output

Input Sample #1

4 1
6 3 4

Output Sample #1

3

Input Sample #2

4 2
6 3 4
6 2 2

Output Sample #2

3
5

Input Sample #3

5 3
1 2 2
2 2 2
12 5 5

Output Sample #3

2
5
3

Notes

Data Size and Constraints

For $100\%$ of the data: $2 \le N \le 10^4$, $1 \le K \le 10^3$, $1 \le X \le N^2$, $1 \le R, C \le N$.

Notes

• This problem is worth $100$ points.
• This problem is translated from COCI2008-2009 CRCI2008-2009 TABLICA, translated by @tearing.

见题面 Input 部分

见题面 Output 部分