== include(page="template/taskheader" task_id="keymess") ==

Poveste şi cerinţă...

 
Breasla Aventurierilor te-a trimis intr-o misiune prin Labirintul Bitilor, unde fiecare poarta este incuiata cu o cheie magica. Exista exact n chei, fiecare inscriptioanta cu un numar de la 0 la n-1. Dar, evident… cineva le-a amestecat complet! Nimeni nu mai stie ce cheie se afla in ce locas. O adevarata harababura — un Keymess.
 
Singura ta unealta? O masinarie ciudata si pe jumatate stricata, numita Oracolul Bitwise.
 
Daca ii oferi doua chei diferite i si j, in loc sa iti spuna exact ce sunt, Oracolul sopteste doar AND-ul bitwise al numerelor lor:
interogare(i, j) = a[i] & a[j]
 
Maistrii Breslei rad nebuneste:
"Daca vrei sa deschizi portile si sa supravietuiesti in acest labirint, trebuie sa afli valoarea fiecarei chei! Dar ai grija: Oracolul cere tribut la fiecare intrebare, asa ca trebuie sa rezolvi totul cu cat mai putine interogari!"
 
Sarcina ta: reconstruieşte intreaga permutare amestecata de chei a[0..n-1] folosind numarul minim posibil de intrebari catre Oracol.
 

h2. Date de intrare

Fişierul de intrare $keymess.in$ ...

Fişierul de intrare $dispozitiv.in$ este organizat astfel:
 
Pe prima linie se află $T$, numărul de teste.
 
Pentru fiecare test:
 
* Pe prima linie se află $N$, $K$.
* Pe a doua linie se afla string-ul binar $a$ de lungime $N$.
* Pe a treia linie se află numărul $Q$.
* Pe următoarele $Q$ linii se află câte un număr $p$, cu semnificaţia că Regele Gheaţă a inversat bit-ul $p$.

h2. Date de ieşire

În fişierul de ieşire $keymess.out$ ...

În fişierul de ieşire $dispozitiv.out$ se va afişa astfel:
 
* Pentru fiecare test, se vor afişa $Q$ linii. Pe fiecare linie se va afla $YES$, daca toate valorile pot fi făcute $0$ sau $NO$ altfel.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ T ≤ 10 000$
* $1 ≤ K ≤ N ≤ 200 000$
* $1 ≤ Q ≤ 200 000$
 
* Fie $S_N$ suma tuturor $N$-urilor dintr-un test de evaluare. Se garantează că $S_N ≤ 200 000$.
* Fie $S_Q$ suma tuturor $Q$-urilor dintr-un test de evaluare. Se garantează că $S_Q ≤ 200 000$.
 
 
 
|_. #  |_. Punctaj |_. Restricţii |
| 1 | 6 | $S_N, S_Q <= 200$ |
| 2 | 15 | $S_N, S_Q <= 2 000$ |
| 3 | 7 | $K = N$ |
| 4 | 15 | $K = 2$ |
| 5 | 24 | $K &le; 10$ |
| 6 | 33 | Fără alte restricţii |

h2. Exemplu

table(example). |_. keymess.in |_. keymess.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

|_. dispozitiv.in |_. dispozitiv.out |
| 3
5 2
01100
3
1
2
3
7 3
1010110
5
2
7
4
1
5
10 5
0011001001
2
2
3 | YES
NO
YES
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
 
 
 
 
 
 
     a
|

h3. Explicaţie

...

În primul test, şirul este iniţial $01100$ şi putem inversa substring-uri de lungime exact $K = 2$. $01100$ poate fi transformat în $00000$ prin inversarea substring-ului $[2, 3]$.
 
După prima actualizare, şirul devine $11100$. Se pare că acesta nu poate fi transformat în $00000$.
 
După a doua actualizare, şirul devine $10100$, care poate fi transformat în şir de zerouri prin inversarea substring-ului $[1, 2]$ (şirul devine $01100$), apoi prin inversarea substring-ului $[2, 3]$.

== include(page="template/taskfooter" task_id="keymess") ==
 

== include(page="template/taskfooter" task_id="dispozitiv") ==