TABLIC - Tablica

Giới hạn
  • Thời gian: 0.237s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Ivo có một bảng kích thước N×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 ≤ 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 2 ), 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

  • Người up: racer
  • Nguồn bài: COCI 2008/2009 - Croatian Regional