시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB48201555.556%

문제

두 명의 학생이 1이상 n이하의 정수를 외치는 게임을 하고 있다. 첫 번째 학생이 먼저 정수를 외친 후 두 명의 학생이 교대로 정수를 외친다. 이전 학생이 외친 정수가 a이면 현재 학생은 (a + 1)이상 (a + k)이하의 정수를 외쳐야 한다. 맨 처음 첫 번째 학생은 1이상 k이하의 정수를 외쳐야 한다. 추가로, 두 명의 학생이 외칠 수 없는 정수 목록이 주어지고, 두 명의 학생은 목록에 있는 정수를 외칠 수 없다. 마지막에 정수를 못 외치는 학생이 게임을 진다. 현재 학생이 외칠 수 있는 정수가 여러 개이면, 외칠 수 있는 정수 중 하나를 외친다. 두 명의 학생이 규칙에 맞게 플레이했을 때, 첫 번째 학생이 이기면 1을 출력하고 두 번째 학생이 이기면 0을 출력한다.

입력

첫 번째 줄에 nk가 공백을 사이에 두고 순서대로 주어진다.

두 번째 줄에 두 명의 학생이 외칠 수 없는 서로 다른 정수가 빈칸을 사이에 두고 오름차순으로 주어진다.

출력

첫 번째 줄에 첫 번째 학생이 이기면 1을 출력하고, 두 번째 학생이 이기면 0을 출력한다.

제한

  • 1 ≤ n ≤ 100,000
  • 1 ≤ k ≤ 100
  • 두 명의 학생이 외칠 수 없는 서로 다른 정수 목록의 개수는 1보다 크거나 같고 n보다 작거나 같다.
  • 두 명의 학생이 외칠 수 없는 정수는 1보다 크거나 같고 n보다 작거나 같은 양의 정수이다.

서브태스크

번호배점제한
130

1 ≤ n, k ≤ 20

270

1 ≤ n ≤ 100,000
1 ≤ k ≤ 100

예제 입력 1

3 2
1

예제 출력 1

0

첫 번째 학생이 맨 처음 외칠 수 있는 정수는 2이다. 첫 번째 학생이 2를 외치면 두 번째 학생이 3을 외쳐서 첫 번째 학생이 진다.

예제 입력 2

4 2
2 3

예제 출력 2

1

첫 번째 학생이 맨 처음 외칠 수 있는 정수는 1이다. 첫 번째 학생이 1을 외치면 두 번째 학생이 외칠 수 있는 정수가 없어서 첫 번째 학생이 이기게 된다.

예제 입력 3

4 2
1 2

예제 출력 3

0

첫 번째 학생이 외칠 수 있는 정수가 없으므로 첫 번째 학생이 진다.

출처

채점 및 기타 정보

  • 예제는 채점하지 않는다.