Ivo có một bảng kích thước ~N \times N~. Bảng được ghi các số từ ~1~ đến ~N^{2}~ liên tiếp theo thứ tự từ trái sang phải và từ trên xuống dưới. Các thao tác sau có thể được thực hiện trên bảng:

1. Xoay một hàng -- tất cả các ô trên hàng đó bị xoay sang phải, sao cho số ở cột cuối cùng được chuyển lên đầu.
2. Xoay một cột -- tất cả các ô trên cột đó bị xoay xuống dưới, sao cho số ở hàng cuối cùng được chuyển lên đầu.

Ivo muốn chuyển số ~X~ đến ô ~(R~, ~C)~ và thực hiện theo các bước sau:

• Trong khi ~X~ chưa ở cột ~C~, xoay hàng chứa nó.
• Trong khi ~X~ chưa ở hàng ~R~, xoay cột chứa nó.

Ivo muốn chuyển ~K~ số theo thứ tự lần lượt. Viết một chương trình tính số thao tác cần thực hiện.

Input

Dòng đầu chứa hai số nguyên ~N~ ~(2 \leq N \leq 10 000)~ và ~K~ ~(1 \leq K \leq 1000)~, mô tả kích thước của bảng và số lượng số cần chuyển.

Mỗi dòng trong số ~K~ dòng tiếp theo chứa ba số nguyên ~X~ ~(1 \leq X \leq N^{2})~, ~R~ và ~C~ ~(1 \leq R~, ~C \leq N)~, thể hiện việc chuyển số mà Ivo muốn thực hiện. Ivo chuyển các số theo thứ tự mà chúng được cho trong input.

Output

In ra ~K~ dòng; với mỗi lượt chuyển số, in ra số lượng thao tác cần thực hiệ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