타일 |
---|
KOI 고등학교에서는 1 × 1의 정사각형 타일을 사용하여 N × N 사각 벽화를 만들고 문화 축제에서 전시할 계획이다. 타일의 색상은 빨강, 파랑, 노랑의 3 종류이다. 벽화 디자인은 다음과 같다. 우선 가장 바깥쪽 바퀴에 빨간색 타일을 붙여 그 안쪽의 둘레에 파란색 타일을 붙인다. 또한 그 안쪽의 둘레에 노란색 타일을 붙인다. 이것을 N × N의 사각형이 가득 때까지 반복한다. 가진 타일의 색상은 바깥쪽 바퀴부터 순서대로 빨강, 파랑, 노랑, 빨강, 파랑, 노랑, ...이다. 문화제가 다가온 어느 날, 벽화 중 K 장의 타일이 벗겨져있는 것을 발견했다. 그래서 새로운 타일을 구입하여 벗겨진 부분에 새로운 타일을 부착했다. 입력으로 벽화의 한 변의 길이 N과 벗겨지는 타일의 매수 K, K 개의 벗겨지는 타일 위치가 주어질 때 벗겨지는 타일의 색상을 요구하는 프로그램을 작성하시오. 예를 들어, N = 11의 경우 11 × 11의 벽화는 그림과 같다. 또한, N = 16이면 16 × 16의 벽화는 그림과 같다.
|
입력 | |
---|---|
입력 데이터는 2+K로 구성된다. 첫 번째는 벽화의 한 변의 길이 N (1 ≦ N ≦ 1000000000 = 10 9 )가 두 번째에는 벗겨지는 타일의 매수 K (1 ≦ K ≦ 1000)이 적혀있다. 2 + i 번째 행 (1 ≦ i ≦ K)는 2 개의 정수 A I 와 b I (1 ≦ A I ≦ N 1 ≦ b I ≦ N)가 공백으로 구분하여 작성하고, i 번째 이 없어 타일이 왼쪽에서 A I 번째 위에서 b I 라인 타일임을 나타낸다. 입력 라인 3에서 2 + K 행에 같은 타일을 나타내는 행이 중복 나타나는 것은 아니다. 또한, 주어진 입력 데이터 40 %는 N ≦ 1000을 충족시키고 있다. |
출력 | |
---|---|
출력은 K 라인으로 구성된다. 각 행은 하나의 정수로부터되어, i 번째 행 (1 ≦ i ≦ K)의 정수는 i 번째 벗겨지는 타일이 빨간색 때는 1을, 파랑의 경우 2를, 노란색 때 3 대표한다. 입력 예 1에서 11 × 11의 벽화는 다음의 그림과 같다. "×"는 벗겨지는 타일을 나타낸다. |
예시 | |||
---|---|---|---|
1 | 입력 | 11 4 5 2 9 7 4 4 3 9 | |
출력 | 2 3 1 3 | ||
2 | 입력 | 16 7 3 7 5 2 11 6 15 2 9 7 8 12 15 16 | |
출력 | 3 2 3 2 1 2 1 |