Description

Xiao Q has an $N \times N$ table. If $N = 4$, then he fills $1$ into the cell in row $1$, column $1$, $2$ into row $1$, column $2$, $\cdots$, $5$ into row $2$, column $1$, $\cdots$, $15$ into row $4$, column $3$, and $16$ into row $4$, column $4$.

Now, Xiao Q performs the following operations on the table:

1. Shift a row: shift all cells in a row to the right, so that the number in the last column moves to the first column.

2. Shift a column: shift all cells in a column downward, so that the number in the last row moves to the first row.

Xiao Q wants to move a number $X$ to the cell $(R, C)$, so he performs the following steps:

• When $X$ is not in column $C$, shift the row that contains $X$.
• When $X$ is not in row $R$, shift the column that contains $X$.

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

Xiao Q wants to move $K$ numbers. What is the minimum number of operations needed?

Input Format

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

In the next $K$ lines, each line contains:

• Three integers $X, R, C$, as described above.

Output Format

Output $K$ lines in total. For each query:

• Output the minimum number of moves needed.

4 1
6 3 4

3

4 2
6 3 4
6 2 2 

3
5

5 3
1 2 2
2 2 2
12 5 5

2
5
3

Hint

Constraints

For $100\%$ of the testdata: $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

• The full score for this problem is $100$ points.
• This problem is translated from COCI2008-2009 CRCI2008-2009 TABLICA, translator
  https://www.luogu.com.cn/user/219791

Translated by ChatGPT 5