고장난 통신 장치

Anna와 Bruno는 고고학자다. 두 사람은 이란의 유적을 조사하고 있다.

역할은 다음과 같다. Anna는 유적을 방문해 유물을 발견하고, Bruno는 기지에서 그 결과를 분석한다.

조사 기간은 $Q$(= 1000)일이다. 매일 Anna는 통신 장치로 그날의 결과를 Bruno에게 보낸다. 하루의 결과는 정수 $X$로 표현된다.

Anna는 하루에 통신 장치를 한 번만 사용할 수 있다. 이 장치는 0과 1로 이루어진 길이 $N$(= 150)의 수열을 보낼 수 있다.

그런데 이 장치는 고장났다. 길이 $N$의 수열에는 고장난 위치가 여러 곳 있다. 고장난 위치에서는 Anna가 설정한 값과 관계없이 항상 0이 전송된다. Anna는 수열을 보낼 때 고장난 위치를 확인할 수 있지만, Bruno는 그 위치를 알지 못한다. 고장난 위치와 그 개수는 날마다 바뀔 수 있다.

조사가 지연될 위험이 있다. 여러분은 이란 국제 프로그래밍 대회 참가 후보자이므로, Anna와 Bruno는 조사 결과를 전송하는 프로그램을 작성해 달라고 요청한다.

Anna와 Bruno 사이의 통신을 구현하는 프로그램 두 개를 작성하라.

• 첫 번째 프로그램은 수열의 길이 $N$, 보낼 정수 $X$, 고장난 위치의 개수 $K$, 고장난 위치 $P$를 받아 Anna가 보낼 수열 $S$를 정한다.
• 두 번째 프로그램은 Bruno가 받은 수열 $A$를 받아 정수 $X$를 복원한다.

정상적으로 작동하는 위치에서는 $S$와 $A$의 값이 같다. 고장난 위치에서는 $S$의 값과 관계없이 $A$의 값이 항상 0이다.

샘플 채점기는 표준 입력에서 다음 데이터를 읽는다.

• 첫 줄에는 정수 $Q$가 주어진다.
• 이어서 $Q$개의 질의 정보가 주어진다.
• 각 질의 정보는 두 줄로 이루어진다.
  • 첫 줄에는 공백으로 구분된 정수 세 개 $N$, $X$, $K$가 주어진다. 이는 보낼 수열의 길이가 $N$, Anna가 보낼 정수가 $X$, 고장난 위치가 $K$개라는 뜻이다.
  • 둘째 줄에는 공백으로 구분된 정수 $K$개 $P_0, P_1, \cdots, P_{K-1}$이 주어진다. 이는 각 $i$ ($0 \le i \le K - 1$)에 대해 수열의 $P_i$번째 위치가 고장났다는 뜻이다.

프로그램이 정상적으로 종료되면 샘플 채점기는 표준 출력에 다음 정보를 쓴다. (따옴표는 실제로 쓰지 않는다.)

• 프로그램이 오답으로 판정되면 Wrong Answer [1] 형식으로 오답 유형을 쓰고, 프로그램은 종료된다.
• Anna를 호출하는 모든 함수 호출이 오답으로 판정되지 않으면 Accepted와 $L^*$의 값을 쓴다. $L^*$의 값은 채점 항목을 참고하라.

여러 유형의 오답에 해당하면 샘플 채점기는 그중 하나만 보고한다.

• $Q = 1000$.
• $N = 150$.
• $0 \le X \le 10^{18}$.
• $1 \le K \le 40$.
• $0 \le P_i \le N - 1$ ($0 \le i \le K - 1$).
• $P_i < P_{i+1}$ ($0 \le i \le K - 2$).