8. Opitý za volantom

V Krajine samých pijanov sú čoraz častejšie pristihnutí vodiči za volantom pod vplyvom alkoholu. To, či je to spôsobené lepšou kvalitou policajnej hliadky, alebo či to súvisí s parádnym hitom vinárskeho trhu s názvom “pangalaktický dunihlav”, je pre všetkých záhadou.

Situácia v krajine ale začína byť vážna – ľudia sa štítia pitia alkoholu, pretože sa boja, že by mohli skončiť za volantom následkom čoho začína celá ekonomika upadať.

Časom si policajné hliadky všimli, že sa vodiči často sťažujú na dopravné značky – buď ich nie je dobre vidno, alebo sú im otočené chrbtom, alebo ich v spoločensky unavenom stave nestihnú zaregistrovať¹.

Prišli teda s nasledujúcim famóznym nápadom: každý vodič bude mať úžasné zariadenie. Vodič sa môže v prípade potreby zariadenia spýtať na všetky dopravné obmedzenia, ktoré sa ho momentálne týkajú. Stačí stlačiť veľké priateľské tlačidlo PODLIEHAM PANIKE a zariadenie vypíše zoznam všetkých predpisov.

Úloha

Na jednej dlhej ceste platia na rôznych úsekoch rôzne dopravné obmedzenia. Každé dopravné obmedzenie je určené jeho začiatkom, koncom a poradovým číslom. Pozície na ceste sú reprezentované celými číslami.

Ak sa vodič nachádza na pozícii \(p\), dopravné obmedzenie so začiatkom \(l\) a koncom \(r\) sa ho týka práve vtedy, keď \(l \leq p < r\).

Dostanete zoznam začiatkov a koncov \(n\) obmedzení a následne \(q\) otázok. Otázka je jedno číslo – pozícia vodiča na ceste. Pre každú otázku vypíšte zoznam všetkých obmedzení, ktoré sa vodiča týkajú.

Otázky je nutné spracovať online – nemôžete spracovať ďalšiu otázku, kým nezodpoviete tú aktuálnu.

Formát vstupu

Na prvom riadku vstupu je počet dopravných obmedzení – \(n \leq 5 \cdot 10^5\). Nasleduje \(n\) riadkov, na \(i\)-tom z nich je popis dopravného obmedzenia s poradovým číslom \(i\).

Popis dopravného obmedzenia pozostáva z dvoch celých čísel \(l, r\) – jeho začiatok a koniec. Platí \(0 \leq l, r \leq 2n\).

Nasleduje číslo \(q \leq 2n\) – počet otázok. Na každom z ďalších \(q\) riadkov je jedno celé číslo \(p\). Nech \(m\) je aktuálna maska (ktorej výpočet je popísaný v nasledujúcom odseku). Potom pozícia vodiča je \(p \oplus m\) (bitový xor \(p\) a \(m\), v C++ p^m).

Formát výstupu

Pre každú otázku \(p\) vypíšte najprv počet dopravných obmedzení \(d\), ktoré sa vodiča týkajú. Následne vypíšte do toho istého riadku čísla \(a_1, a_2, \ldots, a_d\) – poradové čísla týchto dopravných obmedzení v ľubovoľnom poradí. Čísla oddeľte jednou medzerou, a za posledným číslom ukončite riadok.

Pre prvú otázku je hodnota masky \(m = 0\).

Pre ostatné otázky vypočítame hodnotu masky nasledovne: nech \(m'\) je hodnota masky na predchádzajúcej otázke, a nech odpoveď na ňu bola \(d~ a_1~ a_2~ \ldots ~ a_d\). Potom aktuálnu hodnotu masky vypočítame ako \(m = m' \oplus a_1 \oplus a_2 \oplus \ldots \oplus a_d\).

Je zaručené, že počet čísel na správnom výstupe nebude presahovať \(5 \cdot 10^5 + q\).

Príklady

Input:

4
5 7
3 4
1 2
0 6
8
5
7
6
7
3
3
3
2

Output:

2 0 3
1 3
1 0
0
2 1 3
2 2 3
1 3
1 3