Natasha a descoperit un nou joc pe calculator. Pe un suport se află N biluțe pe care este scris câte un număr si . Jocul constă în alegerea unei biluțe, biluță care se va ridica de pe suport și va pluti în aer pentru si secunde, apoi se va așeza din nou pe poziția ei în suport. În momentul în care o biluță atinge suportul, prima biluță bst din stânga ei și prima biluță bdr din dreapta ei (care nu s-au așezat pe suport în același moment de timp) se vor ridica în aer, fiecare plutind pentru sst , respectiv sdr secunde, după care se vor reașeza în suport, fiecare pe poziția ei. Această mișcare a biluțelor continuă până când Natasha se plictisește și închide calculatorul. Dar asta nu e tot. În timp ce Natasha urmărește mișcarea biluțelor, ea trebuie să răspundă la M întrebări de forma: “Este biluța bk la momentul de timp tk pe suport sau în aer?”.

Cerință

Pentru fiecare din cele M întrebări, răspundeți cu 1 dacă biluța b este pe suport, sau cu 0 dacă biluța este în aer.

Date de intrare

Fișierul de intrare bilute.in conține pe prima linie N, M si P reprezentând numărul de biluțe, numărul întrebărilor, respectiv indicele biluței pe care Natasha o alege la începutul jocului. Pe a doua linie se află N numere, reprezentând timpul, în secunde, de plutire a fiecărei biluțe. Pe următoarele M linii, se vor afla câte două numere, bk si tk , cu semnificația din enunț.

Date de ieșire

Fișierul de ieșire biluțe.out va conține pe fiecare linie 0 sau 1, răspunsul la intrebări, în ordinea din fișierul de intrare.

Restricții și precizări

• 1 ≤ N, M ≤ 100 000
• 1 ≤ si, tk ≤ 200 000
• 1 ≤ bk, P ≤ N
• Momentul t=0 este considerat atunci când prima biluță (cea aleasă de Natasha) atinge suportul.
• Dacă la momentul t o biluță atinge suportul, ea se mai poate ridica în aer începând cu momentul t+1, iar la momentul t se consideră că biluța este pe suport.
  Dacă la momentul t o biluță se ridică în aer, se consideră că la momentul t biluța este în aer.
• Se garantează ca numarul total de plutiri a biluțelor nu va depăși 200 000.
• Pentru 50% din teste N ≤ 200.

Exemplu

bilute.in

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

bilute.out

0
1
1
0
0

Explicații

La momentul 0 ajunge pe suport biluța 3 și va face să sară bilele 2 si 4. La momentul 3 biluța 2 ajunge pe suport și va face să plutească biluța 1 si 3, iar biluța 4 ajunge pe suport la momentul 4 și va face să plutească biluța 2 si 5. La momentul 5 ajunge pe suport biluța 3.