TABLIC - Tablica

Ivo has an N×N table. The table has the integers 1 through N2 inscribed in row-major order. The following operations can be done on the table:

1. Rotate a row – all cells in a single row are rotated right, so that the number in the last column moves to the first.

2. Rotate a column – all cells in a single column are rotated down, so that the number in the last row moves to the first.

Ivo occasionally feels the urge to move a number X to cell (R, C) and proceeds as follows:

  • While X is not in column C, rotate the row it is in.
  • While X is not in row R, rotate the column it is in.

Ivo wants to move K numbers one after another. Write a program that calculates the number of rotations needed.

Input

The first line contains two integers N (2 ≤ N ≤ 10 000) and K (1 ≤ K ≤ 1000), the table dimension and the number of moves.

Each of the following K lines contains three integers X (1 ≤ X ≤ N2), R and C (1 ≤ R, C ≤ N), the description of one move Ivo wants to make. Ivo does the moves in the order in which they are given.

Output

Output K lines; for each move, output the number of rotations needed.

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:1s
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.