죄수들의 도전

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

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

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

• 칠판의 정수를 지우고 음이 아닌 정수를 쓴 뒤 방을 나간다. 이전과 같은 정수를 써도 되고, 다른 정수를 써도 된다. 500명 모두가 방에 들어갔다 나간 경우를 제외하고 도전은 계속된다.
• 동전이 적게 든 가방을 골라 도전을 끝낸다.

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

죄수 한 명이 동전이 적게 든 가방을 정확히 고르면 죄수들이 이긴다. 죄수 한 명이라도 가방을 잘못 고르거나, 500명 모두가 방에 들어갔다 나가는 동안 아무도 동전이 적은 가방을 고르려 하지 않으면 죄수들이 진다.

도전을 시작하기 전에 죄수들은 강당에 모여 세 단계로 이루어진 공통 전략을 정한다.

• 칠판에 쓸 수 있는 음이 아닌 정수의 최댓값 $x$를 정한다.
• 방에 들어갔을 때 칠판에 정수 $i$($0 \le i \le x$)가 쓰여 있으면 어느 가방을 조사할지 정한다.
• 조사한 가방의 동전 개수를 알게 되면 어떻게 행동할지 정한다. 구체적으로, 칠판에 정수 $i$($0 \le i \le x$)가 쓰여 있고 조사한 가방에 동전 $j$개가 들어 있다면, 다음 중 하나를 하기로 정해야 한다. $0$ 이상 $x$ 이하의 정수를 칠판에 쓰거나, 동전이 적은 쪽의 가방을 고른다.

죄수들이 도전에서 이기면 간수는 $x$일 동안 더 가둔 뒤 모두 풀어준다.

당신이 할 일은 죄수들이 이 도전을 이길 수 있는 전략을 고안하는 것이다. 제출한 해법의 점수는 $x$의 값에 따라 달라진다. (자세한 내용은 Subtasks 참조)

• $2 \le N \le 5000$