33276번 - XOR 머신 인터랙티브

문제

당신은 다음과 같은 문제를 두 번 해결해야 한다.

길이 $N$의 수열 $A$와 길이 2ドルN$의 수열 $B$가 있다. 두 번의 문제 해결에서 $N$은 같지만 $A$는 다를 수 있다. 수열 $A$의 내용은 알 수 없고, $B$는 각 문제를 해결하기 시작할 때 모든 원소가 0ドル$이다.

부분 수열의 XOR합이란, 부분 수열에 들어있는 모든 원소를 XOR한 값을 의미한다.

당신은 수열 $A$의 모든 짝수 크기의 부분 수열의 XOR합 중 최댓값을 찾아야 한다.

당신은 다음과 같은 연산을 할 수 있다.

• A $i$ $j$ : $B_i$의 값을 $B_i \oplus A_j$로 바꾼다. 이 연산은 두 번의 문제 해결에서 총합하여 최대 3ドルN$번 할 수 있다.
• C $i$ $x$ : $B_i$의 값을 $B_i \oplus x$로 바꾼다. 이 연산은 두 번의 문제 해결에서 총합하여 최대 2ドルN$번 할 수 있다.
• Q $k$ $v_{1}$ $v_{2}$ $\cdots$ $v_{k}$ : 길이 $k$의 수열 $B_{v_{1}}, B_{v_{2}}, \cdots B_{v_{k}}$의 모든 부분수열의 XOR합 중 최댓값을 찾는다. 이 연산은 두 번의 문제 해결에서 총합하여 최대 2ドル$번 할 수 있으며 $k$의 합은 총합하여 2ドルN$을 넘길 수 없다.
• ! $x$ : 문제의 답 $x$를 알아냈다면 이 연산을 통해 답을 제출할 수 있다.

연산들을 적절히 사용하여 문제의 답을 찾아내 보자.

각 연산을 할 수 있는 횟수 및 Q 연산에서의 $k$의 합이 제한되어 있으며, 자세한 사항은 인터랙션 항목을 참조하여라.

입력

첫째 줄에 수열의 길이 $N$이 주어진다. $(2 \leq N \leq 100,000円)$

숨겨진 수열 $A$의 원소 $A_i$는 모두 0ドル$보다 크거나 같고 5ドル \times 10^8$보다 작거나 같은 정수이다.

이후 당신과 채점 시스템과의 인터랙션이 진행된다.

출력

제한

인터랙션

당신은 표준 출력에 다음 연산을 각 줄에 출력하는 것으로, 채점 시스템과 인터랙션할 수 있다. 각 토큰은 공백으로 구분하며, 각 연산의 끝에 개행문자를 출력하여야 한다.

• A $i$ $j$
  • $B_i$의 값을 $B_i \oplus A_j$로 바꾼다.
  • 1ドル \leq i \leq 2N, 1 \leq j \leq N$
  • 이 연산은 두 번의 문제 해결에서 총합하여 최대 3ドルN$번 할 수 있다.
• C $i$ $x$
  • $B_i$의 값을 $B_i \oplus x$로 바꾼다.
  • 1ドル \leq i \leq 2N, 1 \leq x \leq 2^{31}-1,$ $x$는 정수.
  • 이 연산은 두 번의 문제 해결에서 총합하여 최대 2ドルN$번 할 수 있다.
• Q $k$ $v_1, v_2, \cdots, v_k$
  • 길이 $k$의 수열 $B_{v_1}, B_{v_2}, \cdots, B_{v_k}$의 모든 부분수열의 XOR합 중 최댓값이 다음 줄에 입력된다.
  • 1ドル \le k \le 2N, 1 \le v_i \le 2N,$ $i \neq j$ 이면 $v_i \neq v_j$
  • 이 연산은 두 번의 문제 해결에서 총합하여 최대 2번 할 수 있으며 $k$의 합은 총합하여 2ドルN$을 넘길 수 없다.
• ! $x$ : 문제의 답 $x$를 알아냈다면 이 연산을 통해 답을 제출할 수 있다.
  • 만약 첫 번째 문제를 해결했다면 배열 $B$는 모든 수가 0ドル$으로 초기화되고 새로운 숨겨진 수열 $A$에서 두 번째 문제의 인터렉션이 시작된다.
  • 만약 두 번째 문제를 해결했다면 프로그램을 종료해야 한다.

만약 연산이 잘못된 연산이거나 제한을 초과하였다면 당신은 -1을 다음 줄에 입력받으며 이 입력이 주어질 경우 프로그램을 즉시 종료해야 한다.

Q 연산과 ! 연산 이후에는 표준 출력 버퍼를 비워야 한다.

각 언어별로 표준 출력 버퍼를 비우는 방법은 다음과 같다. 기타 언어의 경우, 언어의 레퍼런스 페이지를 참조하여라.

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

노트

두 정수 $a,ドル $b$에 대해 $a \oplus b$는 $a$와 $b$를 XOR한 값으로 정의한다.

부분 수열은 수열에서 0ドル$개 이상의 수를 제거하여 만든 수열을 의미한다.