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:
- 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.
- 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
Comments