bfs

Copiii de la 402 au auzit clopoțelul și au ieșit repede afară să se joace. Văzând un stâlp foarte mare în mijlocul terenului ei s-au gândit la următorul joc. Inițial s-au împărțit în fete și băieți (în număr de m, respectiv n) și s-au așezat astfel:



Stâlpul e în poziție verticală (înclinare 0). Fiecare jucător are o anumită forță (B[i] - forța băiatului i, F[i] - forța fetei i). Jocul decurge astfel: la fiecare pas, fie băiatul cel mai apropiat de stâlp, fie fata cea mai apropiată de stâlp, va arunca mingea spre stâlp (băiatul spre dreapta, fata spre stânga), după care va ieși din joc. După orice aruncare, stâlpul se va înclina suplimentar în partea opusă aruncătorului cu o valoare egală cu forța acestuia. Bineînțeles, cu cât forța aruncătorului este mai mare, cu atât stâlpul se va înclina mai mult. Mai mult, stâlpul nu va reveni la înclinarea inițială după aruncare.



Cu toate acestea, pentru ca jocul să nu capete întorsături neplăcute de situație, stâlpul nu are voie niciodată să fie înclinat cu o valoare strict mai mare decât S (în niciuna din părți), atât în timpul jocului, cât și la finalul acestuia.

Copiii se întreabă dacă pot găsi o ordine a aruncărilor astfel încât toți să arunce mingea și să respecte restricțiile de mai sus (gradul maxim al stâlpului să se mențină în limitele de siguranță). Totuși doamna profesoară vrea să încingă lucrurile, astfel că în cadrul a Q momente de timp interschimbă două fete sau doi băieți plasați consecutiv. Orice schimbare a doamnei profesoare se păstrează pentru momentele de timp următoare.

Cerință

Voi trebuie să ajutați copiii și să aflați după fiecare interschimbare dacă există o ordine validă a aruncărilor.

Date de intrare

Fișierul bfs.in conține pe prima linie trei numere n, m și S reprezentând numărul de băieți, numărul de fete și înclinarea maximă admisă a stâlpului. Pe a doua linie se vor găsi n numere naturale reprezentând forțele băieților. Pe a treia linie se vor găsi m numere naturale reprezentând forțele fetelor. Pe a patra linie se va găsi Q reprezentând numărul de interschimbări efectuate. Urmează Q linii de forma [B|F] x y, unde [B|F] reprezintă în ce grup se face interschimbarea, iar x și y reprezintă pozițiile între care se realizează interschimbarea.

Date de ieșire

Fișierul bfs.out conține Q linii, astfel pe linia i aflându-se valoarea 1, dacă jocul se poate termina cu succes dupa primele i interschimbări și 0 în caz contrar.

Restricții și precizări

• 1 ≤ n, m, Q ≤ 100 000
• $1 ≤ B[i], F[i], S ≤ 10^9$, pentru orice i
• Pentru fiecare schimbare se garantează că |x - y| = 1
• Se garantează că, înainte de efectuarea primei interschimbări, jocul se poate termina cu succes.
• Pentru teste în valoare de 10 puncte n, m ≤ 100 și Q ≤ 250
• Pentru alte teste în valoare de 20 puncte n, m ≤ 2 500 și Q ≤ 6 000
• Pentru alte teste în valoare de 65 puncte n, m ≤ 100 000 și Q ≤ 35 000

Exemplu

bfs.in

6 3 30000
15000 15000 60000 30000 29805 56555
60000 60000 57187
14
B 2 3
B 2 3
B 2 3
B 2 3
F 2 3
F 2 3
B 2 3
B 2 3
B 3 4
B 3 4
B 2 3
B 2 3
F 2 3
F 2 3

bfs.out

0
1
0
1
0
1
0
1
0
1
0
1
0
1

Explicații

Nu e cazul