죄수들의 도전

감옥에 $500$명의 죄수가 갇혀 있다. 어느날, 간수는 감옥에서 나갈 수 있는 기회를 주었다. 간수가 방 안에 동전이 든 두 개의 가방 A와 B를 놓았다. 각 가방에는 $1$ 개 이상 $N$ 개 이하의 동전이 들어 있다. 두 가방에 든 동전의 개수는 다르다. 간수는 죄수들에게 도전 기회를 준다. 죄수들의 목표는 동전이 적게 든 가방을 찾는 것이다.

방에는 동전이 든 가방 외에도 칠판이 있다. 칠판에는 항상 정수 하나만 쓸 수 있다. 처음에는 칠판에 $0$이 쓰여 있다.

간수는 죄수들에게 한명씩 차례로 방에 들어오게 한다. 모든 죄수는 다른 죄수중 누가 자기보다 먼저 이 방에 들어 왔는지 알지 못하고, 또 자기 앞에 몇 명의 죄수가 방에 들어왔는지도 알지 못한다. 매번 죄수가 방에 들어올 때마다, 칠판에 쓰여진 정수를 읽는다. 이 정수를 읽은 다음, 가방 A와 B 중 하나를 골라야 한다. 다음 이 가방을 조사해서 이 가방에 몇 개의 동전이 있는지 알게 된다. 그 다음 죄수는 다음 두 행동 중 하나를 해야 한다.

• 칠판에 쓰여진 정수를 지우고 음이 아닌 정수를 쓴 다음 방을 나간다. 칠판에 먼저 쓰여진 정수와 같은 정수를 쓸 수도 있고, 다른 정수를 쓸 수도 있다. 도전은 계속 이어진다. ($500$명의 죄수 모두가 방을 들어왔다가 나간 경우를 제외하고)
• 동전이 적게 든 가방을 고르고 도전을 종료한다.

한번 방을 나간 죄수는 간수가 다시 방에 들여보내지 않는다.

만약 죄수 중 한 명이 동전이 적게 든 가방을 정확히 맞추면 죄수들이 도전에서 이긴다. 만약 죄수 중 한 명이라도 동전이 적게 든 가방을 틀리거나, $500$명의 죄수 모두가 방에 들어갔다 나왔지만 동전이 적게 든 가방을 맞추려고 아무도 시도하지 않았다면 죄수들이 진다.

도전을 시작하기 전에, 죄수들은 강당에 모여서 3단계로 이루어지는 다음 공통 전략을 정했다.

• 칠판에 쓸 수 있는 음이 아닌 정수의 최대값 $x$를 정한다.

• 방에 들어갔을 때 칠판에 정수 $i$가 쓰여져 있다면 ($0 \le i \le x$) 어느 가방을 조사할 것인지를 정한다.

• 조사한 가방의 동전 개수를 알게 되면 어떤 행동을 할 것인지를 결정한다. 보다 구체적으로, 칠판에 정수 $i$가 쓰여져 있고 ($0 \le i \le x$) 조사한 가방에 동전 $j$개가 들어 있다면, 다음 두 행동 중 하나를 하는 것으로 결정해야 한다.

  • $0$ 이상 $x$ 이하인 어떤 정수를 칠판에 쓸 지, 또는
  • 어느 가방을 동전이 적은 쪽으로 고를지.

죄수들이 도전에서 이기면, 간수는 죄수들을 $x$일간 더 가둔 다음에 모두 풀어줄 것이다.

당신이 할 일은 죄수들이 이 도전을 이길 수 있는 전략을 고안하는 것이다. (가방 A, B에 있는 동전 개수와 무관하게) 여러분이 제출한 해법의 점수는 $x$의 값에 따라 달라진다. (자세한 내용은 Subtasks 참조)

• $2 \le N \le 5000$