나노버그

이 문제에서는 각 버그가 스파이 또는 요원 중 하나인 버그 집합에서, 스파이나 요원을 드러내지 않고 스파이 버그의 실제 개수를 보여야 한다.

나노버그는 주인의 명령을 따르는 지능형 로봇이다. 보통 염탐, 도청, 다른 나노버그 감시에 바쁘다. 모든 나노버그는 외형이 똑같다.

바르토시와 비베크는 동부 카르텔과 남부 무역 회사, 두 회사의 엔지니어다. 두 사람은 양사 대표가 새 계약을 논의할 동부 카르텔 사무실의 회의실을 조사하고 있다. 둘은 함께 나노버그 $n$개를 붙잡았다. 각 버그는 동부 카르텔의 보안 요원이거나 남부 무역 회사의 스파이다.

앤더스는 SpyTek의 보안 전문가다. 오늘 그의 임무는 바르토시와 비베크가 붙잡은 나노버그 중 스파이와 요원이 각각 몇 명인지 알아내도록 돕는 것이다. 앤더스는 각 버그가 스파이인지 요원인지 알지만, 다른 누구도 그것을 모른다.

앤더스가 보기에 버그 중 스파이는 정확히 $a$개다. 바르토시와 비베크는 표준 절차를 통해 스파이가 $a$개 또는 $b$개라는 것만 알아냈다. 두 수 $a$와 $b$의 차이는 정확히 1이다. 그 밖의 정보는 없다.

나노버그는 비싼 지능형 기계이며 정체가 드러나지 않는 것을 중요하게 여긴다. 앤더스는 각 버그의 주인을 안다. 하지만 어떤 나노버그의 소속, 즉 어느 회사에 속하는지가 엔지니어나 다른 나노버그에게 알려지면, 그 나노버그의 이후 기능과 존재 자체가 위협받는다.

보안 전문가인 앤더스에게는 균형 검사기가 있다. 두 개의 칸과 표시등이 달린 작은 상자다. 앤더스는 각 칸에 나노버그를 넣고 버튼을 누른다. 검사기는 두 회사 각각에 대해, 두 칸에 든 그 회사 나노버그 수가 같은지 확인한다. 두 회사 모두 같으면 표시등은 초록색이고, 그렇지 않으면 빨간색이다.

앤더스는 일련의 검사를 진행한다. 먼저 모든 나노버그를 원하는 순서대로 한 줄에 세운다. 각 검사에서 그는 첫 번째 칸에 일부를, 두 번째 칸에 일부를 넣고 버튼을 누른 뒤 결과를 엔지니어에게 보여 준다. 그리고 모든 나노버그를 원래 자리로 돌려보내 원래 순서를 복원한다. 전체 검사 과정에서 나노버그는 줄에서의 자리에 따라 1부터 $n$까지 번호가 붙는다.

앤더스가 $n$개의 나노버그 중 스파이가 정확히 $a$개임을 엔지니어에게 증명하도록 도우라. 어떤 나노버그의 소속도 드러내지 않아야 한다. 불가능하면 불가능하다고 판정하라.

첫 줄에 세 정수 $n$, $a$, $b$가 주어진다 ($20 \le n \le 50$, $1 \le a, b \le 4$, $|a - b| = 1$). 여기서 $n$은 나노버그의 총 개수다. 바르토시와 비베크는 스파이가 $a$개 또는 $b$개라는 것을 알고 있으며, 앤더스는 스파이의 정확한 개수가 $a$임을 증명해야 한다.

첫 줄에 검사 횟수 $m$ ($0 \le m \le 1000$)을 정수 하나로 출력한다. 모든 조건을 만족시킬 수 없으면 $-1$을 출력한다. 답이 존재하면 검사마다 한 줄씩, 총 $m$줄을 출력한다.

각 검사 줄은 세 부분으로 구성된다. 첫 부분은 첫 번째 칸에 넣는 버그다. 버그 개수를 쓰고, 이어서 그 번호들을 순서와 상관없이 쓴다. 다음에는 결과를 나타내는 문자가 온다. 긍정 결과(초록 표시등)는 '=' (ASCII 61), 부정 결과(빨간 표시등)는 '^' (ASCII 94)다. 그 뒤에 두 번째 칸에 넣는 버그를 첫 번째 칸과 같은 형식으로 쓴다. 모든 내용은 한 줄에 출력하며, 연속된 수나 문자는 하나 이상의 공백으로 구분한다.

한 검사 안에서 같은 버그 번호를 두 번 언급할 수 없다.

예에서 엔지니어들은 잡힌 나노버그 22개 중 스파이가 한 개 또는 두 개라는 것을 안다. 실제로는 정확히 두 개이며, 앤더스의 임무는 그것을 증명하는 것이다. 제시된 답에서 그는 네 번의 검사를 수행한다.

첫 번째 검사는 앞의 여섯 버그에 있는 스파이 수가 다음 여섯 버그에 있는 스파이 수와 같다는 것을 보여 준다. 두 칸의 크기가 같으므로 요원에 대해서도 같은 말이 성립한다. 두 번째 검사 후에는 13, 14, 15, 16, 21번 버그에 있는 스파이 수가 17, 18, 19, 22, 20번 버그에 있는 스파이 수와 같다는 것을 알 수 있다. 세 번째 검사는 13, 14, 17번 버그의 스파이 수가 6, 8, 9번 버그의 스파이 수와 다르다는 것을 보여 준다. 네 번째 검사는 두 칸의 크기가 다르면 항상 부정 결과가 나오므로 정보를 주지 않는다.

스파이가 정확히 한 개였다면 적어도 한 번의 검사에서 결과가 달랐을 것이므로, 스파이는 정확히 두 개여야 한다.