정수를 끝까지 외치자
시간 제한1초메모리 제한512 MB
두 학생이 이전 수보다 1 이상 k 이하 큰 수를 교대로 외치며, 외칠 수 없는 수를 피할 때 최적 플레이에서 승자를 판정합니다.
문제
두 명의 학생이 1이상 n이하의 정수를 외치는 게임을 하고 있다. 첫 번째 학생이 먼저 정수를 외친 후 두 명의 학생이 교대로 정수를 외친다. 이전 학생이 외친 정수가 a이면 현재 학생은 (a + 1)이상 (a + k)이하의 정수를 외쳐야 한다. 맨 처음 첫 번째 학생은 1이상 k이하의 정수를 외쳐야 한다. 추가로, 두 명의 학생이 외칠 수 없는 정수 목록이 주어지고, 두 명의 학생은 목록에 있는 정수를 외칠 수 없다. 마지막에 정수를 못 외치는 학생이 게임을 진다. 현재 학생이 외칠 수 있는 정수가 여러 개이면, 외칠 수 있는 정수 중 하나를 외친다. 두 명의 학생이 규칙에 맞게 플레이했을 때, 첫 번째 학생이 이기면 1을 출력하고 두 번째 학생이 이기면 0을 출력한다.
입력
첫 번째 줄에 n과 k가 공백을 사이에 두고 순서대로 주어진다.
두 번째 줄에 두 명의 학생이 외칠 수 없는 서로 다른 정수가 빈칸을 사이에 두고 오름차순으로 주어진다.
출력
첫 번째 줄에 첫 번째 학생이 이기면 1을 출력하고, 두 번째 학생이 이기면 0을 출력한다.
제한
- 1 ≤ n ≤ 100,000
- 1 ≤ k ≤ 100
- 두 명의 학생이 외칠 수 없는 서로 다른 정수 목록의 개수는 1보다 크거나 같고 n보다 작거나 같다.
- 두 명의 학생이 외칠 수 없는 정수는 1보다 크거나 같고 n보다 작거나 같은 양의 정수이다.