Minimum Operations to Shift Table Cells

Little Q has an \(N\times N\) table filled with the numbers \(1,2,\ldots,N^2\) in row–major order. That is, when \(N=4\) the numbers are placed as follows:

\(1\) in cell \((1,1)\), \(2\) in cell \((1,2)\), \(3\) in cell \((1,3)\), \(4\) in cell \((1,4)\); \(5\) in cell \((2,1)\); and so on until \(16\) in cell \((4,4)\).

There are two allowed operations:

1. Row Shift: Cyclically shift a row to the right by one. In other words, in a row shift the number in the last column moves to the first column and every other number moves one column to the right.
2. Column Shift: Cyclically shift a column down by one. In a column shift the number in the last row moves to the first row and every other number moves one row down.

For a given number \(X\) that is initially in cell \((r,c)\) (with \(r=\lceil X/N \rceil\) and \(c=X-(r-1)\cdot N\)), Little Q wants to move it to a target cell \((R,C)\) using operations in the following order:

1. If \(X\) is not in the \(C\text{-th}\) column, repeatedly shift its row until it is. Note that a row shift does not change the row index.
2. If \(X\) is not in the \(R\text{-th}\) row, repeatedly shift its column until it is. A column shift does not change the column index.

If we view the operations in aggregate, notice that each row \(r\) can be shifted a total of \(A_r\) times (with \(0\le A_r<N\)) and each column (after the row shifts) can be shifted a total of \(B_c\) times (with \(0\le B_c<N\)). Then for a number originally at \((r,c)\) that must reach \((R,C)\) we need:

\[ \begin{aligned} c+A_r &\equiv C \pmod{N},\\ r+B_C &\equiv R \pmod{N}. \end{aligned} \]

Thus the required shifts for that number are:

\[ A_r=(C-c)\mod N,\quad B_C=(R-r)\mod N. \]

Since a single row (or column) shift is applied to every number in that row (or column), if multiple queries involve the same row or the same target column they can share the operations. In other words, for all queries the minimal total number of operations is the sum of the required shifts for each distinct row involved plus the sum of the required shifts for each distinct target column involved. It is guaranteed that if a row (or column) is involved in several queries the computed required shift is consistent.

Your task is to compute the minimal total number of operations to move all \(K\) given numbers to their respective target cells.

inputFormat

The first line contains two integers \(N\) and \(K\) \( (1\le N\le 10^5, 1\le K\le 10^5)\), where \(N\) is the size of the table and \(K\) is the number of queries.

Each of the next \(K\) lines contains three integers: \(X\), \(R\), and \(C\) \( (1\le X\le N^2, 1\le R,C\le N)\). The integer \(X\) represents the number to be moved, and \((R,C)\) is its target cell.

outputFormat

Output a single integer representing the minimal number of operations required to move all \(K\) numbers to their target cells.

sample

4 1
6 3 4

3

</p>