Bánh có một bảng kích thước ~n \times n~ được điền các số từ ~1~ đến ~n^2~ theo thứ tự từ trái qua phải và từ trên xuống dưới.

Có hai thao tác cơ bản được thực hiện trên bảng như sau:

1. Xoay một hàng – tất cả các ô trong một hàng được xoay sang phải, sao cho số ở cột cuối cùng di chuyển đến ô đầu tiên.

2. Xoay một cột – tất cả các ô trong một cột được xoay xuống, sao cho số ở hàng cuối cùng di chuyển đến ô đầu tiên.

Vậy muốn di chuyển một số ~x~ tới một ô ~(r, c)~ ta tiến hành như sau:

• Khi ~x~ không ở trong cột ~c~, hãy xoay hàng chứa nó.

• Khi ~x~ không ở trong hàng ~r~, hãy xoay cột chứa nó.

Sau đây là ví dụ về cách di chuyển số 6 đến ô (3, 4) trong bảng ~4 \times 4~, bắt đầu từ cấu hình ban đầu:

$$\displaystyle \begin{bmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 \end{bmatrix}% \begin{bmatrix} 1 & 2 & 3 & 4 \\ 8 & 5 & 6 & 7 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 \end{bmatrix}% \begin{bmatrix} 1 & 2 & 3 & 4 \\ 7 & 8 & 5 & 6 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 \end{bmatrix}% \begin{bmatrix} 1 & 2 & 3 & 16 \\ 7 & 8 & 5 & 4 \\ 9 & 10 & 11 & 6 \\ 13 & 14 & 15 & 12 \end{bmatrix} $$

Input

Dòng đầu tiên chứa hai số nguyên ~n, k~ thỏa ~2 \le n \le 10000, 1 \le k \le 1000~. Kích thước bàn và số lần cần di chuyển ô.

Mỗi dòng trong k dòng sau chứa ba số nguyên ~x, r, c~ thỏa ~1 \le x \le n^2; 1 \le r, c \le n~.

Output

Ứng với mỗi yêu cầu di chuyển in ra số thao tác xoay cần thiết để đến được ô cần đến.

Sample Input 1

4 1
6 3 4

Sample Output 1

3

Sample Input 2

4 2
6 3 4
6 2 2

Sample Output 2

3
5

Sample Input 3

5 3
1 2 2
2 2 2
12 5 5

Sample Output 3

2
5
3