문제
정현이네 학교에서는 1 × 1 사각형의 타일을 사용하여 N × N 사각 벽화를 만들어 문화제에 전시할 예정이다. 타일의 색상은 빨강, 파랑, 노랑의 3 종류이다. 벽화 디자인은 다음과 같다. 먼저 가장 바깥 쪽 둘레에 붉은 타일을 붙이고 그 안쪽에 둘레에 파란색 타일을 붙인다. 또한 그 안쪽 둘레에 노란색 타일을 붙인다. 이를 N × N의 사각형이 가득 될 때까지 반복한다. 사용 타일의 색상은 가장 바깥 둘레부터 순서대로 빨강, 파랑, 노랑, 빨강, 파랑, 노랑, ...이다.
문화제가 다가오는 어느 날, 벽화 중 K 개의 타일이 벗겨져있는 것으로 밝혀졌다. 그래서 새 타일을 구입하여 벗겨진 부분에 새 타일을 부착하려고 한다. 입력으로 벽화의 한 변의 길이 N과 벗겨진 타일의 갯수 K, K개의 벗겨진 타일의 위치가 주어 졌을 때, 각 위치의 벗겨진 타일 색상을 구하는 프로그램을 작성하라.
예를 들어, N = 11의 경우 11 × 11의 벽화 디자인은 아래와 같다.
입력
입력은 총 2 + K 라인으로 구성된다.
첫 번째 줄에는 벽화의 한 변의 길이 N (1 <= N <= 1,000,000,000)가
두 번째 줄에는 벗겨진 타일의 매수 K (1 <= K <= 1,000)가 입력된다.
세 번째 행에서부터 K (1 <= i <= K)개의 행에 걸쳐 각 행에는 2 개의 정수 Ci와 Ri (1 <= Ci, Ri <= N)가 공백으로 구분하여 입력된다. Ci는 열 번호이고 Ri는 행 번호임에 유의하라.
입력 예 1에서 11 × 11의 벽화는 다음 그림과 같다. "×"는 벗겨진 타일을 나타낸다.
출력
출력은 K 개의 행으로 구성된다. 각 행은 하나의 정수를 출력하며, i 번째 줄 (1 <= i <= K)의 정수는 i 번째 벗겨진 타일이 빨간색이면 1을, 파랑의 경우 2를 노란색이면 3으로 출력한다.
예제1
입력
11
4
52
97
44
39
출력
2
3
1
3
예제2
입력
16
7
37
52
116
152
97
812
1516
출력
3
2
3
2
1
2
1
출처
joi 2010/2011 예선 3