Ivo có một bảng kích thước N×N. Bảng được ghi các số từ 1 đến N² 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 ≤ N ≤ 10 000) và K (1 ≤ K ≤ 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 ≤ X ≤ N²), R và C (1 ≤ R, C ≤ 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.

Example

Input
4 1
6 3 4

Output
3


Input
4 2
6 3 4
6 2 2

Output
3
5


Input
5 3
1 2 2
2 2 2
12 5 5

Output
2
5
3