Cerința

După ce au vizitat toate obiectivele turistice din municipiul Iaşi, Ioana şi Maria au inventat un joc.

Ele au la dispoziţie un număr de n cutii aranjate în linie dreaptă, numerotate în ordine de la 1 la n, şi un număr de m bile ce pot fi aşezate în unele dintre aceste cutii. Unele cutii sunt deteriorate, astfel că bilele dispar dacă sunt puse în acele cutii.

O mutare constă în alegerea unei bile şi poziţionarea ei în una din cutiile învecinate (precedenta sau următoarea ). Bilele pot fi mutate după următoarea regulă: când o bilă a fost mutată pentru prima dată într-o anumită direcţie, atunci bila îşi păstrează direcţia de deplasare la următoarele mutări (de exemplu, dacă o bilă a fost mutată pentru prima dată spre stânga atunci orice mutări ulterioare ale acestei bile se pot face doar spre stânga).

Jocul se termină atunci când nici un jucător nu mai poate face nici o mutare. Pierde primul jucător care nu mai poate face nici o mutare. Fetele joacă un număr de T astfel de jocuri. Ştiind că Ioana este prima care face o mutare, iar apoi fetele mută alternativ, se cere să se stabilească pentru fiecare din cele T jocuri dacă ea are sau nu o strategie sigură de câştig.

Date de intrare

Fişierul .in conţine pe prima linie un număr natural T, care reprezintă numărul de jocuri pe care le joacă cele două fete.

Pe următoarele linii fişierul conţine, în ordine, descrierea celor T jocuri. Fiecare joc este descris prin câte 3 linii:

• prima linie va conţine, în ordine, trei numere naturale n, k, m separate prin câte un singur spaţiu (n reprezintă numărul de cutii, k reprezintă numărul de cutii deteriorate şi m reprezintă numărul de bile)
• a doua linie va conţine k numere naturale, separate prin câte un singur spaţiu, reprezentând numerele de ordine ale cutiilor deteriorate
• a treia linie va conţine m numere naturale reprezentând numerele de ordine ale cutiilor care conţin bile la începutul jocului.

Date de ieșire

Fişierul .out va conţine pe prima linie un şir de T valori de 0 şi 1 neseparate prin spaţii, având următoarea semnificaţie: valoarea de pe poziţia i din şir (i={1,2,…,T}) este 1 daca jocul i este câştigat de Ioana sau 0 dacă jocul i este pierdut de Ioana.

Restricții și precizări

• 1 ≤ T ≤ 10
• 1 ≤ n ,m ≤ 10000
• 0 ≤ k ≤ 10000
• se consideră că din prima nu poate fi mutată o bilă spre stânga, iar din ultima nu se poate muta o bila spre dreapta;
• iniţial nici o bilă nu se află în prima , în ultima sau într-o deteriorată;
• în fişierul de intrare poziţiile bilelor şi cele ale cutiilor deteriorate sunt sortate crescător;

Exemplu:

cutie.in

2
10 1 1
6
3
10 1 2 
5 
4 4 

cutie.out

10

Explicație

Pentru primul joc, Ioana are o strategie sigură de câştig (pentru a câştiga va muta bila la dreapta), iar pentru al doilea joc nu are o strategie sigură de câştig.