안나와 브루노는 고고학자입니다. 그들은 이란에서 유적을 조사하고 있습니다.

그들의 임무는 다음과 같습니다: 안나는 유적을 방문하여 유물을 발견하고, 브루노는 베이스캠프에서 그 결과를 분석합니다.

조사는 $Q(=1\,000)$일 동안 예정되어 있습니다. 매일 안나는 통신 장치를 사용하여 브루노에게 결과를 보냅니다. 각 날의 결과는 하나의 정수 $X$로 표현됩니다.

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

하지만 이 장치는 고장 나 있었습니다. 길이 $N$인 수열에는 몇 군데의 고장 난 위치가 있습니다. 고장 난 위치에서는 실제로 설정한 값과 관계없이 항상 값 $0$을 보냅니다. 안나가 수열을 보낼 때 그녀는 고장 난 위치들을 볼 수 있습니다. 하지만 브루노는 그 위치들을 알지 못합니다. 고장 난 위치들과 고장 난 위치의 개수는 매일 바뀔 수 있습니다.

조사가 지연될 위험이 있습니다. 당신은 이란에서 열리는 국제 프로그래밍 대회의 참가 후보자이므로, 안나와 브루노는 당신에게 조사 결과를 전송하는 프로그램을 작성해 달라고 요청했습니다.

과제

안나와 브루노 사이의 통신을 수행하는 두 프로그램을 작성하십시오.

• 수열의 길이 $N$, 전송할 정수 $X$, 고장 난 위치의 개수 $K$, 그리고 고장 난 위치들 $P$가 주어졌을 때, 첫 번째 프로그램은 안나가 보낼 수열 $S$를 설정합니다.
• 브루노가 받은 수열 $A$가 주어졌을 때, 두 번째 프로그램은 정수 $X$를 복원합니다.

통신 장치가 정상 작동하는 위치에서는 수열 $S$와 수열 $A$가 같은 값을 가집니다. 고장 난 위치에서는 수열 $S$의 값과 관계없이 수열 $A$가 항상 값 $0$을 가집니다.

구현 세부 사항

같은 프로그래밍 언어로 작성된 두 개의 파일을 제출해야 합니다.

첫 번째 파일은 Anna.c 또는 Anna.cpp입니다. 이 파일은 안나가 보낼 수열을 설정하며, 다음 함수를 구현해야 합니다. 프로그램은 Annalib.h를 포함해야 합니다.

• void Anna( int N, long long X, int K, int P[] )

  각 테스트 케이스마다 이 함수는 $Q=1\,000$번 호출됩니다.

  • 매개변수 N은 전송할 수열의 길이입니다.
  • 매개변수 X는 전송할 정수입니다.
  • 매개변수 K는 고장 난 위치의 개수입니다.
  • 매개변수 P[]는 고장 난 위치들을 나타내는 길이 $K$인 수열입니다.

  함수 Anna 내에서는 다음 함수를 호출해야 합니다.

  • void Set( int pos, int bit )

    이 함수는 통신 장치로 보낼 수열 $S$의 한 비트를 설정합니다.

    • 매개변수 pos는 설정할 위치입니다. pos는 $0$ 이상 $N-1$ 이하의 정수여야 합니다. 위치는 $0$부터 번호가 매겨진다는 점에 유의하십시오. 이 범위를 벗어난 매개변수로 호출되면 프로그램은 오답(Wrong Answer[1])으로 판정됩니다. 같은 매개변수 pos로 이 함수를 두 번 이상 호출하는 것은 허용되지 않습니다. 같은 매개변수로 두 번 이상 호출되면 프로그램은 오답(Wrong Answer[2])으로 판정됩니다.
    • 매개변수 bit는 수열의 pos번째 위치에 설정할 값입니다. bit의 값은 $0$ 또는 $1$이어야 합니다. 다른 매개변수로 호출되면 프로그램은 오답(Wrong Answer[3])으로 판정됩니다.

  함수 Set은 함수 Anna 내에서 정확히 $N$번 호출되어야 합니다. 함수 Anna가 종료될 때 함수 Set이 호출된 횟수가 $N$과 다르면 프로그램은 오답(Wrong Answer[4])으로 판정됩니다.

  안나의 함수 호출이 잘못된 것으로 판정되면 프로그램은 즉시 종료됩니다.

두 번째 파일은 Bruno.c 또는 Bruno.cpp입니다. 이 파일은 조사 결과를 나타내는 정수를 복원하며, 다음 함수를 구현해야 합니다. 프로그램은 Brunolib.h를 포함해야 합니다.

• long long Bruno( int N, int A[] )

  각 테스트 케이스마다 이 함수는 $Q=1\,000$번 호출됩니다.

  • 매개변수 N은 브루노가 받은 수열의 길이입니다.
  • 매개변수 A는 길이 $N$인 정수 수열입니다. 이는 브루노가 받은 수열입니다.
  • 함수 Bruno는 $X$의 값을 복원하여 반환해야 합니다.

채점 절차

채점은 다음과 같은 방식으로 이루어집니다. 프로그램이 오답(Wrong Answer)으로 판정되면 즉시 종료됩니다.

1. cnt = 0으로 설정합니다.
2. 함수 Anna를 한 번 호출합니다.
3. 함수 Anna가 설정한 수열을 $S$라고 합시다. 수열 $S$에서 $P$에 속한 위치들의 값을 $0$으로 바꾸어 수열 $A$를 얻습니다. 매개변수 $A$로 함수 Bruno를 한 번 호출합니다.
4. cnt = cnt +1로 설정합니다. 만약 $\mathrm{cnt}<Q$이면 (2)로 이동합니다. 만약 $\mathrm{cnt}=Q$이면 (5)로 이동합니다.
5. 프로그램의 점수가 계산됩니다.

중요 공지 사항

• 실행 시간과 메모리 사용량은 채점 절차의 (1), (2), (3), (4)에 대해 계산됩니다.
• 프로그램은 (2)의 Anna 함수 호출이나 (3)의 Bruno 함수 호출에서 오답(Wrong Answer)으로 판정되지 않아야 합니다. 프로그램은 런타임 에러 없이 실행되어야 합니다.
• 프로그램은 내부 사용을 위해 다른 함수를 구현하거나 전역 변수를 사용할 수 있습니다. 제출된 프로그램은 그레이더와 함께 컴파일되어 하나의 실행 파일이 됩니다. 다른 파일과의 충돌을 피하기 위해 모든 전역 변수와 내부 함수는 static으로 선언해야 합니다. 실제 채점 시에는 안나와 브루노의 프로그램이 2개의 별도 프로세스로 실행되므로 전역 변수를 공유할 수 없습니다.
• 채점 과정에서 Anna와 Bruno 함수는 각각 $Q=1\,000$번씩 호출됩니다. 프로그램에서 사용하는 변수들은 적절히 초기화되어야 합니다.
• 프로그램은 표준 입력과 표준 출력을 사용해서는 안 됩니다. 프로그램은 어떤 방법으로든 다른 파일과 통신해서는 안 됩니다.

컴파일 및 테스트 실행

대회 웹페이지에서 프로그램을 테스트할 수 있는 샘플 그레이더가 포함된 압축 파일을 다운로드할 수 있습니다. 압축 파일에는 프로그램의 샘플 소스 파일도 포함되어 있습니다.

샘플 그레이더는 grader.c 또는 grader.cpp 중 하나의 소스 파일로 구성됩니다. 예를 들어, 프로그램이 Anna.c와 Bruno.c이거나 Anna.cpp와 Bruno.cpp인 경우 다음 명령어를 실행하여 프로그램을 컴파일할 수 있습니다.

• C

  gcc -std=c11 -O2 -o grader grader.c Anna.c Bruno.c -lm

• C++

  g++ -std=c++14 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

컴파일에 성공하면 실행 파일 grader가 생성됩니다.

실제 그레이더는 샘플 그레이더와 다르다는 점에 유의하십시오. 샘플 그레이더는 단일 프로세스로 실행되며, 표준 입력에서 입력 데이터를 읽고 결과를 표준 출력에 씁니다.

샘플 그레이더의 입력

샘플 그레이더는 표준 입력에서 다음 데이터를 읽습니다.

• 첫 번째 줄에는 정수 $Q$가 주어집니다.
• 그다음 $Q$개의 쿼리에 대한 정보가 주어집니다.

• 각 쿼리의 정보는 다음과 같이 두 줄로 구성됩니다.

  • 첫 번째 줄에는 공백으로 구분된 세 정수 $N$, $X$, $K$가 주어집니다. 이는 전송할 수열의 길이가 $N$이고, 안나가 보낼 정수가 $X$이며, 고장 난 위치가 $K$개임을 의미합니다.
  • 두 번째 줄에는 공백으로 구분된 $K$개의 정수 $P_0,P_1,\cdots,P_{K-1}$이 주어집니다. 이는 각 $i$ ($0\le i\le K-1$)에 대해 수열의 $P_i$번째 위치가 고장 났음을 의미합니다.

샘플 그레이더의 출력

프로그램이 성공적으로 종료되면 샘플 그레이더는 표준 출력에 다음 정보를 씁니다. (따옴표는 실제로 출력되지 않습니다.)

• 프로그램이 오답(Wrong Answer)으로 판정되면 샘플 그레이더는 “Wrong Answer [1]”과 같은 형식으로 그 종류를 출력하고 프로그램이 종료됩니다.
• Anna에 대한 모든 함수 호출이 오답으로 판정되지 않으면 샘플 그레이더는 “Accepted”와 $L^*$의 값을 출력합니다. $L^*$의 값에 대해서는 서브태스크를 참조하십시오.

프로그램이 여러 종류의 오답에 해당하더라도 샘플 그레이더는 그중 하나만 보고합니다.

제한

모든 입력 데이터는 다음 조건을 만족합니다.

• $Q=1000$.
• $N=150$.
• $0\le X\le 1\,000\,000\,000\,000\,000\,000$.
• $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$).

서브태스크

• 이 과제의 모든 테스트 케이스에 대해 다음 값의 최솟값을 $L^*$라고 합시다.

  • $K\le L$인 모든 쿼리에 대해 브루노가 올바른 $X$ 값을 답하는 최대 정수 $L\le40$.

• 이 과제의 점수는 다음과 같은 방식으로 계산됩니다:

  • 만약 $L^*=0$이면 점수는 0점입니다.
  • 만약 $1\le L^*\le14$이면 점수는 8점입니다.
  • 만약 $15\le L^*\le37$이면 점수는 $(L^*-15)\times2+41$점입니다.
  • 만약 $38\le L^*\le40$이면 점수는 $(L^*-38)\times5+90$점입니다.

예제

다음은 그레이더를 위한 예제 입력과 이에 해당하는 함수 호출입니다. 다음 예제는 $Q=2$, $N=3$이므로 이 과제의 제한 조건을 만족하지 않는다는 점에 유의하십시오.

입력 1

2
3 14 1
2
3 9 2
0 1

예제 호출

여기서 Anna(...), Bruno(...), Anna(...), Bruno(...)의 매개변수는 다음과 같습니다.