문제
준혁이는 타일로 작품을 만드는 예술가이다. 크기가 N × N인 작품을 만들기 위해서
준혁이는 1 × 1 타일을 사용한다.
색상은 빨강, 파랑, 노랑 중 하나이다.
작품은 가장 바깥쪽에 빨간색을 붙이고, 그 안쪽에 파란색을 붙이고,
그 안쪽에 노란색을 붙이는 방법으로 만든다. 이것을 N × N 정사각형이 가득 찰 때까지 반복한다.
타일 색은 바깥 쪽부터 순서대로 빨강, 파랑, 노랑, 빨강, 파랑, 노랑, ...이다.
준혁이의 놀라운 미적 감각을 질투하는 은수는 작품에 K개 타일을 제거했다.
준혁이는 새로운 타일을 구입하여, 제거된 부분에 새로운 타일을 붙이려고 한다.
작품의 한 변의 크기 N, 은수가 제거한 타일의 개수 K와 위치가 주어졌을 때,
제거된 타일의 색상을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 한 변의 길이 N이 주어진다. (1 ≤ N ≤ 100,000,000)
둘째 줄에는 은수가 제거한 타일의 개수 K가 주어진다. (1 ≤ K ≤ 1,000)
다음 줄부터 K개 줄에는 은수가 제거한 타일의 위치 a_i, b_i가 제거한 순서대로 주어진다.
(1 ≤ ai ≤ N, 1 ≤ bi ≤ N)
타일은 왼쪽에서 ai번째, 위에서 bi번째에 있다.
같은 타일을 두 번 이상 제거하는 경우는 없다.
출력
은수가 제거한 순서대로 타일의 색상을 출력한다.
빨간색은 1, 파란색은 2, 노란색은 3을 출력한다.
예제1
입력
11
4
52
97
44
39
출력
2
3
1
3
출처
20201031 집중강화학습3차2번,dennisstar,JOI2011 예선 3번