TABLIC - Tablica

Ivo có một bảng kích thước N×N. Bảng được ghi các số từ 1 đến N2 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 ≤ N2), 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

Được gửi lên bởi:Race with time
Ngày:2009-02-17
Thời gian chạy:0.237s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:COCI 2008/2009 - Croatian Regional

hide comments
2013-09-20 07:02:36 a;slkfjasl;fkj
Ivo là invoker ^^

Last edit: 2013-09-20 07:09:57
2010-11-19 18:26:36 dpcm
có thể làm với N <= 10^9.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.