문제

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

길이 의 수열 와 길이 의 수열 가 있다. 두 번의 문제 해결에서 은 같지만 는 다를 수 있다. 수열 의 내용은 알 수 없고, 는 처음에 모두 0으로 되어있다.

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

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

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

• A : 의 값을 xor 로 바꾼다. 이 연산은 두 번의 문제 해결에서 총합하여 최대 번 할 수 있다.
• C : 의 값을 xor 로 바꾼다. 이 연산은 두 번의 문제 해결에서 총합하여 최대 번 할 수 있다.
• : 길이 의 수열 의 모든 부분수열의 xor 합중 최댓값을 찾는다. 이 연산은 두 번의 문제 해결에서 총합하여 최대 2번 할 수 있으며 의 합은 총합하여 을 넘길 수 없다.
• ! : 문제의 답 를 알아냈다면 이 연산을 통해 답을 제출 할 수 있다.

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

인터랙션

첫째 줄에 수열의 길이 이 주어진다.

숨겨진 수열 A의 원소는 는 모두 0보다 크거나 같고 보다 작거나 같은 정수이다.

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

당신은 채점 시스템에게 다음과 같은 연산을 할 수 있다.

A

• 의 값을 xor 로 바꾼다.

• 이 연산은 두 번의 문제 해결에서 총합하여 최대 번 할 수 있다.

C

• 의 값을 xor 로 바꾼다.
• 이 연산은 두 번의 문제 해결에서 총합하여 최대 번 할 수 있다.

Q

• 길이 의 수열 의 모든 부분수열의 xor 합중 최댓값이 다음 줄에 입력된다.
• 이 연산은 두 번의 문제 해결에서 총합하여 최대 2번 할 수 있으며 의 합은 총합하여 을 넘길 수 없다.

! : 문제의 답 를 알아냈다면 이 연산을 통해 답을 제출 할 수 있다.

• 만약 첫번째 문제를 해결했다면 배열 는 초기화 되고 새로운 숨겨진 배열 에서 두 번째 문제의 인터렉션이 시작된다.
• 만약 두 번째 문제를 해결했다면 프로그램을 종료해야 한다.

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

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

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

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