Table Rotation

Time limit1sMemory limit128 MB

Summary

Simulate row and column rotations on an N x N table to move K numbers to given target cells in order, counting total rotations for each move.

Level: Medium5 of 10
Topics: Simulation, Implementation, Math
Solved: No attempts yet

Problem

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.

Row rotation: choose one row and rotate it one cell to the right. The number in the last column moves to the first column.
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.

Input

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.

Output

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

Examples3

Example 1
Input
```
4 1
6 3 4
```
Expected output
```
3
```
Example 2
Input
```
4 2
6 3 4
6 2 2
```
Expected output
```
3
5
```
Example 3
Input
```
5 3
1 2 2
2 2 2
12 5 5
```
Expected output
```
2
5
3
```