8. Obmedzený pohyb

Farmár Bob sa nedávno rozhodol, že si na svoju farmu dá konečne zaviesť inžinierske siete. Už o pár dní sa mu to na záhrade len tak hemžilo robotníkmi kopajúcimi dlhočizné jamy pre rôzne káble a potrubia. Firma, ktorá túto robotu robila, však nanešťastie skrachovala a Boba nechala s rozkopanou záhradou. Bob sa však po záhrade potrebuje pohybovať, musí sa predsa starať o petržlen, baklažán, cibuľku, jahody … Keďže skákanie cez jamy je príliš nebezpečné, obchádzať sa mu ich nechce a zasypávanie všetkých jám by trvalo príliš dlho, zobral Bob niekoľko dosák a položil ich krížom cez niektoré jamy ako mosty.

Po čase však Bob zistil, že niektoré z týchto dosák by sa mu zišli pri oprave plota. Rozhodol sa teda niektoré jamy zasypať, aby tým nejaké dosky uvoľnil. Ale ktoré? Zišlo by sa mu pre každú jamu vedieť, ktoré dosky cez ňu vlastne vedú.

Úloha

Na záhrade je \(n\) jám očíslovaných \(1, 2, \dots, n\) a \(m\) dosák očíslovaných \(1, 2, \dots, m\). Jamy aj dosky budeme pre jednoduchosť považovať za úsečky v rovine. Žiadne dve jamy nemajú spoločný bod, ani žiadne dve dosky nemajú spoločný bod. Navyše platí, že každá doska sa pretína s práve jednou jamou (pod pojmom “pretína sa” myslíme, že úsečky majú práve jeden spoločný bod a tento bod nie je koncovým bodom žiadnej z nich). Na vstupe dostanete zadané pozície všetkých jám aj dosák. Pre každú jamu vypíšte zoznam dosák, ktoré ju pretínajú.

Formát vstupu

V prvom riadku vstupu sú dve celé čísla \(n, m\) (\(1 \leq n, m \leq 50\,000\)) – počet jám a počet dosák. V každom z nasledujúcich \(n\) riadkov je popis jednej jamy. Popis jamy tvoria štyri celé čísla \(x_1, y_1, x_2, y_2\) \((-1\,000\,000 \leq x_1, y_1, x_2, y_2 \leq 1\,000\,000)\), ktoré popisujú to, že daná jama má koncové body \((x_1, y_1)\) a \((x_2, y_2)\). V nasledujúcich \(m\) riadkoch sú popisy dosák, v rovnakom formáte. Jamy aj dosky sú očíslované v poradí, v akom sú uvedené na vstupe.

Formát výstupu

Pre každú jamu (v poradí, ako sú očíslované), vypíšte jeden riadok. Tento riadok má obsahovať čísla dosák, ktoré túto jamu pretínajú, oddelené presne jednou medzerou, vo vzostupnom poradí. V prípade, že jamu nepretína žiadna doska, vypíšte pre ňu prázdny riadok.

Príklad

Input:

3 4
1 -1 1 4
-1 -2 -3 0
4 3 5 0
3 1 -1 1
3 5 -2 2
5 5 4 -4
3 -1 -1 0

Output:

1 2 4

3

Situácia na Bobovej záhrade vyzerá nasledovne (plné čiary sú jamy, prerušované čiary sú dosky):