24733번 - 이것도 XOR해 보시지 인터랙티브

동전 수집가 승재는 동전을 무게별로 분류해 가지고 있었다. 하지만 어디선가 고양이가 나타나 동전을 마구잡이로 섞으며 "이것도 XOR해 보시지!"라는 정체불명의 대사만 남기고 사라져버렸다! 한낱 고양이에게 질 수 없었던 승재는 직접 만든 XOR-저울을 이용해 동전을 다시 분류하기로 한다.

XOR-저울은 양팔 저울을 개조한 것으로, 양쪽의 무게를 각각 잰 후 그 XOR값을 반환한다. 하지만, 개조 과정에서 문제가 있었는지 한쪽이라도 비어있다면 작동하지 않는다.

승재가 수집한 동전에는 몇 가지 규칙이 있다.

1. 동전을 $1$g짜리부터 순서대로 수집했기 때문에, 동전의 최대 무게가 $k$g이라면 $1 \leq p \leq k$인 모든 정수 $p$에 대해 무게가 $p$g인 동전이 존재한다.
2. $k$는 $2 \times 2^m-2(m \geq 2)$가 아니라는 조건을 만족한다. 하지만 멍청하게도 $k$값이 정확히 몇인지는 기억하지 못한다.
3. 동전의 번호는 $0$번부터 $n-1$번까지로 라벨링이 되어있다.

위 조건들을 이용해 승재를 도와 동전을 모두 분류해보자.

첫 번째 줄에 동전의 개수 $n$이 주어진다. $(k \leq n \leq 10\,000)$ 이때 동전의 번호는 $0$번부터 $n-1$번까지이다.

동전의 최대 무게 $k$는 주어지지 않는다. $(3 \leq k \leq 1\,000$, $k \neq 2 \times 2^m-2$, $m \geq 2)$

다음을 표준 출력 스트림(stdout)으로 한 줄에 출력하여, 동전 무게의 합의 xor 값을 알아낼 수 있다.

• $?$ $a_0$ $\cdots$ $a_{i-1}$ $-1$ $b_0$ $\cdots$ $b_{j-1}$ $-1$: XOR-저울을 사용해 $(c_{a_0}$ $+$ $\cdots$ $+$ $c_{a_{i-1}})$ $\oplus$ $(c_{b_0}$ $+$ $\cdots$ $+$ $c_{b_{j-1}})$을 출력한다. $c_q$는 $q$번째 동전의 무게이며, $a_0,$ $\cdots,$ $a_{i-1},$ $b_0,$ $\cdots,$ $b_{j-1}$은 서로 다른 동전의 번호이다. $(i \geq 1,$ $j \geq 1,$ $i+j \leq n)$

각 질문을 출력한 후에는 반드시 표준 출력 버퍼를 flush 해야 하고, 표준 입력 스트림(stdin)을 통해 질문에 대한 답을 입력받아야 한다. 그렇지 않으면, 시간 초과 또는 런타임에러를 받는다.

질문하는 $a_0,$ $\cdots,$ $a_{i-1},$ $b_0,$ $\cdots,$ $b_{j-1}$의 범위가 동전 번호를 벗어나는 경우, 틀렸습니다를 받는다.

질문은 최대 $n-1$번 할 수 있고, 이보다 더 많이 질문을 하면 틀렸습니다를 받는다.

최대 $n-1$번의 질문을 이용해, 정답을 아래의 표준 출력 스트림(stdout)을 이용해 한 번만 출력한다.

• $!$ $c_0$ $\cdots$ $c_{n-1}$: 모든 동전의 무게를 순서대로 출력한다.

그 후 반드시 표준 출력 버퍼를 flush해야 하고, 프로그램을 종료한다. 이것은 질문 횟수에 포함되지 않는다.

출력 후에는 표준 출력 버퍼를 flush해 주어야 한다. 언어 별로 표준 출력 버퍼를 flush하는 방법은 다음과 같다.

• C: fflush(stdout)
• C++: std::cout << std::flush
• Java: System.out.flush()
• Python: sys.stdout.flush()