Anna 和 Bruno 是考古學家。他們正在調查伊朗的遺跡。

他們的分工如下：Anna 造訪遺跡並發掘文物，Bruno 則在基地營分析調查結果。

他們預計進行 $Q\,(=1\,000)$ 天的調查。每天，Anna 都會使用通訊裝置將結果傳給 Bruno。每天的結果以一個整數 $X$ 表示。

Anna 每天只能使用通訊裝置一次。它可以傳送一個長度為 $N\,(=150)$、由 0 和 1 組成的序列。

然而，裝置故障了。長度為 $N$ 的序列中有若干故障位置。在故障位置，無論實際設定的值為何，傳出的值總是 0。Anna 傳送序列時，可以看見故障位置，但 Bruno 不知道這些位置。故障位置及其數量每天都可能改變。

他們的調查可能因此延誤。由於你是伊朗某場國際程式競賽的選手候選人，Anna 和 Bruno 請你撰寫程式，傳送他們的調查結果。

任務

請撰寫兩個程式，實現 Anna 和 Bruno 之間的通訊。

• 第一個程式會獲得序列長度 $N$、要傳送的整數 $X$、故障位置的數量 $K$，以及故障位置 $P$，並設定 Anna 要傳送的序列 $S$。
• 第二個程式會獲得 Bruno 收到的序列 $A$，並還原整數 $X$。

在通訊裝置正常運作的位置，序列 $S$ 和序列 $A$ 的值相同。在故障位置，無論序列 $S$ 的值為何，序列 $A$ 的值總是 0。

實作細節

你需要提交兩個以相同程式語言撰寫的檔案。

第一個檔案是 Anna.c 或 Anna.cpp。此檔案負責設定 Anna 要傳送的序列，並實作下列函式。程式應引入 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$ 開始編號。若使用超出範圍的參數呼叫，程式會被判為答案錯誤 [1]。不得以相同的參數 pos 呼叫此函式超過一次；若以相同參數呼叫超過一次，程式會被判為答案錯誤 [2]。
    • 參數 bit 是設定在序列第 pos 個位置的值。bit 的值必須是 0 或 1；若使用其他值呼叫，程式會被判為答案錯誤 [3]。

  在函式 Anna 中，必須恰好呼叫 Set 共 $N$ 次。當 Anna 結束時，若呼叫 Set 的次數不等於 $N$，程式會被判為答案錯誤 [4]。

  若 Anna 進行的函式呼叫被判為不合法，程式就會終止。

第二個檔案是 Bruno.c 或 Bruno.cpp。此檔案負責還原表示調查結果的整數，並實作下列函式。程式應引入 Brunolib.h。

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

  對每筆測試資料，此函式會被呼叫 $Q=1\,000$ 次。

  • 參數 N 是 Bruno 收到的序列長度。
  • 參數 A 是長度為 $N$ 的整數序列，即 Bruno 收到的序列。
  • 函式 Bruno 必須還原並回傳 $X$ 的值。

評測流程

評測按照以下方式進行。如果程式被判為答案錯誤，會立即終止。

1. 設定 $\mathrm{cnt}=0$。
2. 呼叫函式 Anna 一次。
3. 令 $S$ 為函式 Anna 設定的序列。將 $S$ 中屬於 $P$ 的位置設為 0，得到序列 $A$。以 $A$ 為參數呼叫函式 Bruno 一次。
4. 設定 $\mathrm{cnt}=\mathrm{cnt}+1$。若 $\mathrm{cnt}<Q$，回到步驟 (2)；若 $\mathrm{cnt}=Q$，前往步驟 (5)。
5. 為你的程式計分。

重要注意事項

• 執行時間和記憶體用量以評測流程的步驟 (1)、(2)、(3)、(4) 計算。
• 程式在步驟 (2) 的 Anna 呼叫或步驟 (3) 的 Bruno 呼叫中，都不得被判為答案錯誤。程式執行時不得發生執行期錯誤。
• 程式可以實作其他內部使用的函式，或使用全域變數。提交的程式會和評測程式一起編譯成單一執行檔。所有全域變數及內部函式都應宣告為 static，以避免與其他檔案衝突。由於 Anna 和 Bruno 的程式在正式評測時會以兩個不同的行程執行，因此不能共享全域變數。
• 在一個行程中，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$、Anna 要傳送的整數為 $X$，且有 $K$ 個故障位置。
  • 第二行包含 $K$ 個以空白分隔的整數 $P_0,P_1,\ldots,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 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^*$ 為本題所有測試資料中，下列數值的最小值。

  • 滿足以下條件的最大整數 $L \le 40$：對每個 $K \le L$ 的詢問，Bruno 都回答正確的 $X$ 值。

• 本題分數按以下方式計算：

  • 如果 $L^*=0$，得 $0$ 分。
  • 如果 $1 \le L^* \le 14$，得 $8$ 分。
  • 如果 $15 \le L^* \le 37$，得 $(L^*-15)\times 2+41$ 分。
  • 如果 $38 \le L^* \le 40$，得 $(L^*-38)\times 5+90$ 分。

範例

以下是範例評測程式的輸入及相應的函式呼叫。注意，由於 $Q=2,N=3$，以下範例不符合本題的資料範圍。

輸入格式 1

2
3 14 1
2
3 9 2
0 1

函式呼叫 1

這裡 Anna(...)、Bruno(...)、Anna(...)、Bruno(...) 的參數依序如下。