joi 2010/2011 예선 3- 3색 타일 (Tile) > 문제은행 : 정보올림피아드&알고리즘




2891 : 3색 타일 (Tile)

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
45 회   
시도횟수
93 회   

문제

정현이네 학교에서는 1 × 1 사각형의 타일을 사용하여 N × N 사각 벽화를 만들어 문화제에 전시할 예정이다. 타일의 색상은 빨강, 파랑, 노랑의 3 종류이다. 벽화 디자인은 다음과 같다. 먼저 가장 바깥 쪽 둘레에 붉은 타일을 붙이고 그 안쪽에 둘레에 파란색 타일을 붙인다. 또한 그 안쪽 둘레에 노란색 타일을 붙인다. 이를 N × N의 사각형이 가득 될 때까지 반복한다. 사용 타일의 색상은 가장 바깥 둘레부터 순서대로 빨강, 파랑, 노랑, 빨강, 파랑, 노랑, ...이다.


문화제가 다가오는 어느 날, 벽화 중 K 개의 타일이 벗겨져있는 것으로 밝혀졌다. 그래서 새 타일을 구입하여 벗겨진 부분에 새 타일을 부착하려고 한다. 입력으로 벽화의 한 변의 길이 N과 벗겨진 타일의 갯수 K, K개의 벗겨진 타일의 위치가 주어 졌을 때, 각 위치의 벗겨진 타일 색상을 구하는 프로그램을 작성하라.

 

예를 들어, N = 11의 경우 11 × 11의 벽화 디자인은 아래와 같다.



또한 N = 16의 경우 16 × 16의 벽화 디자인은 아래와 같다.

 

 


입력형식

입력은 총 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으로 출력한다.

입력 예

11
4
5 2
9 7
4 4
3 9

출력 예

2
3
1
3

입력 예

16
7
3 7
5 2
11 6
15 2
9 7
8 12
15 16

출력 예

3
2
3
2
1
2
1


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP