题目描述

小 Q 有一张 $N \times N$ 的表格。若 $N = 4$，那么他将 $1$ 填入第一列第一行，$2$ 填入第二列第一行，$\cdots$，$5$ 填入第一列第二行，$\cdots$，$15$ 填入第三列第四行，$16$ 填入第四列第四行。

现在，小 Q 对该表格作如下操作：

1. 移动行：向右移动一行中的所有单元格，以使最后一列中的数字移到第一列。

2. 移动列：向下移动一列中的所有单元格，以使最后一行中的数字移到第一行。

小 Q 想把一个数字 $X$ 移到单元格 $(R,C)$，于是进行如下操作：

• 当 $X$ 不在第 $C$ 列时，移动它所在的行。
• 当 $X$ 不在第 $R$ 行时，移动它所在的列。

下面是一个如何将数字 $6$ 移动到单元格 $(3, 4)$ 的例子。

小 Q 想移动 $K$ 个数字，问至少要进行多少次操作。

输入格式

第一行，两个正整数 $N$ 和 $K$，分别表示表格大小和移动次数。

接下来，$K$ 行，对于每一行：

• 三个整数 $X, R, C$，含义见题目描述。

输出格式

共 $K$ 行，对于每一行：

• 对每个询问，输出至少移动的次数。

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

提示

数据规模及约定

对于 $100\%$ 的数据：$2 \le N \le 10^4$，$1 \le K \le 10^3$，$1 \le X \le N^2$，$1\le R,C \le N$。

说明

• 本题满分 $100$ 分。
• 本题译自 COCI2008-2009 CRCI2008-2009 TABLICA，译者
  https://www.luogu.com.cn/user/219791