Anna dan Bruno adalah arkeolog. Mereka sedang meneliti reruntuhan di Iran.

Pembagian tugas mereka adalah sebagai berikut: Anna mengunjungi reruntuhan dan menemukan artefak, sedangkan Bruno menganalisis hasilnya di kamp utama.

Penelitian mereka dijadwalkan berlangsung selama $Q(=1\,000)$ hari. Setiap hari, Anna mengirimkan hasilnya kepada Bruno menggunakan sebuah perangkat komunikasi. Hasil setiap hari dinyatakan sebagai sebuah bilangan bulat $X$.

Anna hanya dapat menggunakan perangkat komunikasi tersebut sekali sehari. Perangkat itu dapat mengirimkan barisan sepanjang $N(=150)$ yang terdiri dari 0 atau 1.

Namun, perangkat itu rusak. Ada beberapa posisi yang rusak dalam barisan sepanjang $N$ tersebut. Pada posisi yang rusak, perangkat selalu mengirimkan nilai 0, apa pun nilai yang sebenarnya diatur. Ketika Anna mengirimkan sebuah barisan, ia dapat melihat posisi-posisi yang rusak. Namun, Bruno tidak mengetahuinya. Posisi dan banyaknya posisi yang rusak dapat berubah setiap hari.

Ada risiko penelitian mereka akan tertunda. Karena kamu merupakan calon peserta sebuah kompetisi pemrograman internasional di Iran, Anna dan Bruno memintamu menulis program untuk mengirimkan hasil penelitian mereka.

Tugas

Tulislah dua program yang memungkinkan komunikasi antara Anna dan Bruno.

• Diberikan panjang barisan $N$, bilangan bulat yang akan dikirim $X$, banyaknya posisi yang rusak $K$, dan posisi-posisi yang rusak $P$, program pertama mengatur barisan $S$ yang dikirim Anna.
• Diberikan barisan $A$ yang diterima Bruno, program kedua memulihkan bilangan bulat $X$.

Pada posisi tempat perangkat komunikasi berfungsi, barisan $S$ dan barisan $A$ memiliki nilai yang sama. Pada posisi yang rusak, barisan $A$ selalu bernilai 0, apa pun nilai pada barisan $S$.

Detail Implementasi

Kamu harus mengumpulkan dua berkas yang ditulis dalam bahasa pemrograman yang sama.

Berkas pertama adalah Anna.c atau Anna.cpp. Berkas ini mengatur barisan yang dikirim Anna dan mengimplementasikan fungsi berikut. Program harus menyertakan Annalib.h.

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

  Untuk setiap kasus uji, fungsi ini dipanggil $Q=1\,000$ kali.

  • Parameter $N$ adalah panjang barisan yang akan dikirim.
  • Parameter $X$ adalah bilangan bulat yang akan dikirim.
  • Parameter $K$ adalah banyaknya posisi yang rusak.
  • Parameter P[] adalah barisan sepanjang $K$ yang menjelaskan posisi-posisi yang rusak.

  Di dalam fungsi Anna, fungsi berikut harus dipanggil.

  • void Set( int pos, int bit )

    Fungsi ini mengatur sebuah bit dalam barisan $S$ yang akan dikirim perangkat komunikasi.

    • Parameter $pos$ adalah posisi yang akan diatur. $pos$ harus berupa bilangan bulat antara $0$ dan $N-1$, inklusif. Perhatikan bahwa posisi dihitung mulai dari $0$. Jika fungsi dipanggil dengan parameter di luar rentang ini, programmu dinyatakan sebagai Jawaban Salah [1]. Fungsi ini tidak boleh dipanggil lebih dari sekali dengan parameter $pos$ yang sama. Jika dipanggil lebih dari sekali dengan parameter yang sama, programmu dinyatakan sebagai Jawaban Salah [2].
    • Parameter $bit$ adalah nilai yang diatur pada posisi $pos$ dalam barisan. Nilai $bit$ harus 0 atau 1. Jika fungsi dipanggil dengan parameter lain, programmu dinyatakan sebagai Jawaban Salah [3].

  Fungsi Set harus dipanggil tepat $N$ kali di dalam fungsi Anna. Ketika fungsi Anna berakhir, jika banyaknya pemanggilan fungsi Set berbeda dari $N$, programmu dinyatakan sebagai Jawaban Salah [4].

  Programmu dihentikan jika pemanggilan fungsi oleh Anna dianggap tidak sah.

Berkas kedua adalah Bruno.c atau Bruno.cpp. Berkas ini memulihkan bilangan bulat yang menyatakan hasil penelitian dan mengimplementasikan fungsi berikut. Program harus menyertakan Brunolib.h.

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

  Untuk setiap kasus uji, fungsi ini dipanggil $Q=1\,000$ kali.

  • Parameter $N$ adalah panjang barisan yang diterima Bruno.
  • Parameter $A$ adalah barisan bilangan bulat sepanjang $N$. Inilah barisan yang diterima Bruno.
  • Fungsi Bruno harus memulihkan nilai $X$ dan mengembalikannya.

Prosedur Penilaian

Penilaian dilakukan sebagai berikut. Jika programmu dinyatakan sebagai Jawaban Salah, program langsung dihentikan.

1. Atur $cnt=0$.
2. Panggil fungsi Anna sekali.
3. Misalkan $S$ adalah barisan yang diatur oleh fungsi Anna. Pada barisan $S$, atur nilai 0 pada posisi-posisi dalam $P$ untuk memperoleh barisan $A$. Panggil fungsi Bruno sekali dengan parameter $A$.
4. Atur $cnt=cnt+1$. Jika $cnt<Q$, lanjutkan ke (2). Jika $cnt=Q$, lanjutkan ke (5).
5. Programmu akan diberi nilai.

Catatan Penting

• Waktu eksekusi dan penggunaan memori dihitung untuk langkah (1), (2), (3), (4) dalam Prosedur Penilaian.
• Programmu tidak boleh dinyatakan sebagai Jawaban Salah pada pemanggilan fungsi Anna di (2) atau Bruno di (3). Programmu harus berjalan tanpa galat saat eksekusi.
• Programmu boleh mengimplementasikan fungsi lain untuk penggunaan internal atau menggunakan variabel global. Program yang dikumpulkan akan dikompilasi bersama grader menjadi satu berkas yang dapat dieksekusi. Semua variabel global dan fungsi internal harus dideklarasikan static agar tidak berbenturan dengan berkas lain. Karena program Anna dan Bruno dijalankan sebagai 2 proses terpisah saat dinilai, keduanya tidak dapat berbagi variabel global.
• Dalam proses tersebut, masing-masing fungsi Anna dan Bruno dipanggil $Q=1\,000$ kali. Variabel yang digunakan programmu harus diinisialisasi dengan benar.
• Programmu tidak boleh menggunakan masukan standar dan keluaran standar. Programmu tidak boleh berkomunikasi dengan berkas lain dengan cara apa pun.

Kompilasi dan Uji Coba

Kamu dapat mengunduh sebuah berkas arsip dari halaman web kompetisi yang berisi grader contoh untuk menguji programmu. Arsip tersebut juga berisi berkas kode sumber contoh untuk programmu.

Grader contoh terdiri dari satu berkas kode sumber, yaitu grader.c atau grader.cpp. Sebagai contoh, jika programmu adalah Anna.c dan Bruno.c, atau Anna.cpp dan Bruno.cpp, jalankan perintah berikut untuk mengompilasi programmu.

• 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

Ketika kompilasi berhasil, berkas yang dapat dieksekusi grader akan dibuat.

Perhatikan bahwa grader sebenarnya berbeda dari grader contoh. Grader contoh dijalankan sebagai satu proses yang membaca data dari masukan standar dan menuliskan hasil ke keluaran standar.

Masukan untuk Grader Contoh

Grader contoh membaca data berikut dari masukan standar.

• Baris pertama berisi sebuah bilangan bulat $Q$.
• Berikutnya diberikan informasi tentang $Q$ kueri.

• Informasi setiap kueri terdiri dari dua baris berikut.

  • Baris pertama berisi tiga bilangan bulat $N,X,K$ yang dipisahkan spasi. Ini berarti panjang barisan yang akan dikirim adalah $N$, bilangan bulat yang akan dikirim Anna adalah $X$, dan terdapat $K$ posisi yang rusak.
  • Baris kedua berisi $K$ bilangan bulat $P_0,P_1,\ldots,P_{K-1}$ yang dipisahkan spasi. Ini berarti, untuk setiap $i$ ($0 \le i \le K-1$), posisi $P_i$ dalam barisan rusak.

Keluaran Grader Contoh

Ketika program berakhir dengan sukses, grader contoh menuliskan informasi berikut ke keluaran standar. (Tanda kutip tidak benar-benar dituliskan.)

• Jika programmu dinyatakan sebagai Jawaban Salah, grader contoh menuliskan jenisnya dalam bentuk Wrong Answer [1], dan programmu dihentikan.
• Jika setiap pemanggilan fungsi Anna tidak dinyatakan sebagai Jawaban Salah, grader contoh menuliskan Accepted dan nilai $L^*$. Untuk nilai $L^*$, lihat bagian Penilaian.

Jika programmu dinyatakan sebagai beberapa jenis Jawaban Salah, grader contoh hanya melaporkan salah satunya.

Batasan

Semua data masukan memenuhi kondisi berikut.

• $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$).

Penilaian

• Misalkan $L^*$ adalah nilai minimum dari nilai berikut untuk semua kasus uji pada soal ini.

  • Bilangan bulat terbesar $L \le 40$ sedemikian sehingga, untuk setiap kueri dengan $K \le L$, Bruno menjawab nilai $X$ dengan benar.

• Nilai untuk soal ini dihitung sebagai berikut:

  • Jika $L^*=0$, nilainya 0 poin.
  • Jika $1 \le L^* \le 14$, nilainya 8 poin.
  • Jika $15 \le L^* \le 37$, nilainya $(L^*-15)\times 2+41$ poin.
  • Jika $38 \le L^* \le 40$, nilainya $(L^*-38)\times 5+90$ poin.

Contoh

Berikut adalah contoh masukan untuk grader beserta pemanggilan fungsi yang bersesuaian. Perhatikan bahwa contoh berikut tidak memenuhi batasan soal karena $Q=2$, $N=3$.

Masukan 1

2
3 14 1
2
3 9 2
0 1

Contoh Pemanggilan

Berikut adalah parameter untuk Anna(...), Bruno(...), Anna(...), Bruno(...).