### COCI 2008/2009, Croatian Regional

## Task TABLICA

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

- Rotate a row – all cells in a single row are rotated right, so that the number in the last column moves to the first.
- 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.

Here is an example of how to move number 6 to cell (3, 4), start from the initial configuration:

1 | 2 | 3 | 4 |

5 | 6 | 7 | 8 |

9 | 10 | 11 | 12 |

13 | 14 | 15 | 16 |

1 | 2 | 3 | 4 |

8 |
5 |
6 |
7 |

9 | 10 | 11 | 12 |

13 | 14 | 15 | 16 |

1 | 2 | 3 | 4 |

7 |
8 |
5 |
6 |

9 | 10 | 11 | 12 |

13 | 14 | 15 | 16 |

1 | 2 | 3 | 16 |

7 | 8 | 5 | 4 |

9 | 10 | 11 | 6 |

13 | 14 | 15 | 12 |

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.### Examples

## Sample Input4 1 ## Sample Output3 |
## Sample Input4 2 ## Sample Output3 |
## Sample Input5 3 ## Sample Output2 |

All Submissions

Best Solutions

**Point Value:** 15

**Time Limit:** 1.00s

**Memory Limit:** 32M

**Added:** Apr 29, 2009

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...