题目描述

小明有一个 $N \times N$ 的方阵，按列优先填入 $1$ 到 $N^2$：第一列从上到下填 $1$ 到 $N$，第二列从上到下填 $N+1$ 到 $2N$，以此类推。

方阵支持两种操作：

1. 行平移：将某一行的所有元素整体右移一位，最右端的元素移到最左端。
2. 列平移：将某一列的所有元素整体下移一位，最下端的元素移到最上端。

现在小明想把数字 $X$ 移到第 $R$ 行第 $C$ 列，他按照以下策略操作：

• 如果 $X$ 当前不在第 $C$ 列，先平移 $X$ 所在的行，使 $X$ 到达第 $C$ 列。
• 如果 $X$ 当前不在第 $R$ 行，再平移 $X$ 所在的列，使 $X$ 到达第 $R$ 行。

注意：每次操作会改变方阵中多个元素的位置。小明依次进行 $K$ 次这样的移动，每次移动前数字 $X$ 的位置是当前方阵中的实际位置（受之前操作影响）。

对于每次移动，输出所需的最少操作次数。

输入格式

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

接下来 $K$ 行，每行三个整数 $X, R, C$，表示将数字 $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$。