아이스크림 게임

Kirderf와 Slin은 모두에게 아이스크림이 제공되는 멋진 파티에 일찍 도착했다. 현재 파티장에는 둘만 있으며, 테이블 위에 아이스크림 통 $N$개가 한 줄로 놓여 있다. 아이스크림에는 $K$가지 서로 다른 맛이 있으며, 각 맛은 $0$ 이상 $K - 1$ 이하의 정수로 표현된다.

Slin과 Kirderf는 아이스크림이 몹시 먹고 싶어서 아이스크림 일부를 먹는 게임을 하기로 한다. 두 사람은 번갈아 가며 차례를 진행하고, 한 차례에는 아이스크림 통 하나를 먹는다. 파티 주최자가 언제든지 파티장에 들어올 수 있으므로, Kirderf와 Slin이 아이스크림을 먹었다는 사실이 너무 명백해서는 안 된다. 따라서 통 사이에 빈자리가 생기지 않도록 가장 오른쪽 또는 가장 왼쪽의 아이스크림 통만 먹을 수 있다. 또한 누군가 아이스크림을 먹었다는 사실이 드러나지 않도록 모든 맛의 통이 항상 적어도 하나씩 남아 있어야 한다. 움직일 수 없는 사람이 패배한다.

Kirderf는 Slin에게 지고 싶지 않아서, 게임의 여러 상태에서 누가 필승 전략을 갖는지 판별하는 프로그램을 작성해 달라고 부탁했다. $Q$개의 질의가 주어지며, 각 질의는 구간 $[L, R]$이다. 통 $L, L + 1, \dots, R$만 남아 있을 때 누가 필승 전략을 갖는지 판별해야 한다. 통에는 왼쪽에서 오른쪽으로 $1$부터 $N$까지 번호가 매겨져 있다.

어떤 플레이어가 필승 전략을 갖는다는 것은 상대가 어떤 수를 두더라도 그 플레이어가 항상 게임에서 이길 수 있음을 의미한다. 두 플레이어 중 한 명이 필승 전략을 갖는다는 것을 증명할 수 있다.

점수

각각 일정한 점수가 배정된 여러 테스트 그룹으로 해답을 평가한다. 한 테스트 그룹의 점수를 얻으려면 그 테스트 그룹의 모든 테스트 케이스를 해결해야 한다. 최종 점수는 단일 제출에서 받은 점수 중 최댓값이다.

그룹 | 점수 | 제한

$1$ |$9$| $N,Q \le 15$

$2$ |$11$| $N,Q \le 100$

$3$ |$17$| $N,Q \le 1000$

$4$ |$5$| $K=1$

$5$ |$7$| $K=2$

$6$ |$11$| 각 $1 \le i \le Q$에 대해 $R_i - L_i + 1 \le K+1$

$7$ |$23$| $Q=1$, $L_1=1, R_1=N$

$8$ |$17$| 추가 제한이 없다.

첫째 줄에 세 정수 $N$, $K$, $Q$ ($1 \le K \le N \le 2 \cdot 10^5$, $1 \le Q \le 10^5$)이 주어진다. 둘째 줄에 모두 $0$ 이상 $K - 1$ 이하인 정수 $N$개가 주어진다. 이 정수들은 한 줄로 놓인 아이스크림 통의 맛을 나타낸다. 각 맛은 적어도 한 번 나타난다. 이어지는 $Q$개의 줄에는 두 정수 $L_i$와 $R_i$ ($1 \le L_i \le R_i \le N$)가 주어진다.

각 질의마다 정수 하나씩, $Q$개의 줄에 출력한다. 질의 $[L_i, R_i]$에서 먼저 시작하는 플레이어가 필승 전략을 가지면 $1$을 출력한다. 다른 플레이어가 필승 전략을 가지면 $2$을 출력한다. 마지막으로, 상태가 유효하지 않다면, 즉 구간에 모든 아이스크림 맛이 존재하지 않는다면 $0$을 출력한다.

구간 $[1, 5]$에서는, 즉 아이스크림 $5$개가 모두 남아 있는 경우에는 두 번째 플레이어가 필승 전략을 갖는다. 첫 번째 플레이어가 무엇을 하더라도 두 번째 플레이어에게 가능한 수가 있으며, 그 후에는 통이 $3$개만 남으므로 첫 번째 플레이어가 패배한다.

$[1, 4]$에서는 첫 번째 플레이어가 아이스크림 $1$을 제거하여 이기는 전략을 갖는다.

구간 $[1, 3]$에는 맛 $3$의 아이스크림 통이 없으므로 유효하지 않다.