타일

상근이는 타일로 작품을 만드는 예술가이다. 크기가 N × N인 작품을 만들기 위해서 상근이는 1 × 1 타일을 사용한다. 색상은 빨강, 파랑, 노랑 중 하나이다. 작품은 가장 바깥쪽에 빨간색을 붙이고, 그 안쪽에 파란색을 붙이고, 그 안쪽에 노란색을 붙이는 방법으로 만든다. 이것을 N × N 정사각형이 가득 찰 때까지 반복한다. 타일 색은 바깥 쪽부터 순서대로 빨강, 파랑, 노랑, 빨강, 파랑, 노랑, ...이다.

상근이의 놀라운 미적 감각을 질투하는 창영이는 작품에 K개 타일을 제거했다. 상근이는 새로운 타일을 구입하여, 제거된 부분에 새로운 타일을 붙이려고 한다.

작품의 한 변의 크기 N, 창영이가 제거한 타일의 개수 K와 위치가 주어졌을 때, 제거된 타일의 색상을 구하는 프로그램을 작성하시오.

예를 들어, N = 11인 경우 상근이의 작품은 다음과 같다.

또, N = 16인 경우에는 아래와 같다.

첫째 줄에 한 변의 길이 N이 주어진다. (1 ≤ N ≤ 109) 둘째 줄에는 창영이가 제거한 타일의 개수 K가 주어진다. (1 ≤ K ≤ 1000) 다음 줄부터 K개 줄에는 창영이가 제거한 타일의 위치 ai bi가 제거한 순서대로 주어진다. (1 ≤ ai ≤ N, 1 ≤ bi ≤ N) 타일은 왼쪽에서 ai번째, 위에서 bi번째에 있다. 같은 타일을 두 번 이상 제거하는 경우는 없다.

창영이가 제거한 순서대로 타일의 색상을 출력한다. 빨간색은 1, 파란색은 2, 노란색은 3을 출력한다.