표 회전

N×N 표가 있다. 표에는 1부터 N^2까지의 수가 행 우선 순서(row-major order)로 적혀 있다.

표에는 다음 두 가지 연산을 할 수 있다.

1. 행 회전: 한 행을 골라 오른쪽으로 한 칸 회전시킨다. 마지막 열에 있던 수는 첫 열로 이동한다.
2. 열 회전: 한 열을 골라 아래로 한 칸 회전시킨다. 마지막 행에 있던 수는 첫 행으로 이동한다.

수 X를 위치 (R, C)로 옮길 때는 다음 과정을 따른다.

• X가 C열에 올 때까지, X가 들어 있는 행을 오른쪽으로 회전시킨다.
• X가 R행에 올 때까지, X가 들어 있는 열을 아래로 회전시킨다.

아래 그림은 수 6을 (3, 4)로 옮기는 한 예이다.

총 K개의 수를 차례대로 옮기려고 한다. 한 수를 옮긴 뒤에는 표를 초기 상태로 되돌리지 않고, 그 상태에서 다음 수를 옮긴다. 각 수를 옮기는 데 필요한 회전 횟수를 구하시오.

첫째 줄에 표의 크기 N과 옮기려는 수의 개수 K가 주어진다.

• 2 ≤ N ≤ 10000
• 1 ≤ K ≤ 1000

다음 K개의 줄에는 옮기려는 수 X와 목표 위치 R, C가 주어진다.

• 1 ≤ X ≤ N^2
• 1 ≤ R, C ≤ N

수들은 입력으로 주어진 순서대로 하나씩 옮겨야 한다.

K개의 줄에 걸쳐, 각 수를 옮기는 데 필요한 회전 횟수를 순서대로 출력한다.