Table Rotation

There is an N×N table. The numbers from 1 to N^2 are written in row-major order.

Two operations are available on the table.

1. Row rotation: choose one row and rotate it one cell to the right. The number in the last column moves to the first column.
2. Column rotation: choose one column and rotate it one cell downward. The number in the last row moves to the first row.

To move a number X to position (R, C), use the following process.

• Rotate the row containing X to the right until X is in column C.
• Rotate the column containing X downward until X is in row R.

The figure below shows one way to move the number 6 to (3, 4).

You will move K numbers in order. After moving one number, the table is not reset; the next number is moved from the table's current state. Compute how many rotations are needed for each move.

The first line contains the table size N and the number of values to move, K.

• 2 ≤ N ≤ 10000
• 1 ≤ K ≤ 1000

Each of the next K lines contains a number X and a target position R, C.

• 1 ≤ X ≤ N^2
• 1 ≤ R, C ≤ N

The numbers must be moved one by one in the order given.

Print K lines. On each line, print the number of rotations needed for the corresponding move.