Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: vaiku_zaidimas.in

Rezultatų failas: vaiku_zaidimas.out

Jei norite pateikti savo sprendimą - prisijunkite.

Vaikų žaidimas

Išlaikyti vaikus susidomėjusius pradinėje mokykloje yra išties sunkus darbas! Kažkam reikia mamytės, kažkam skauda pirštą, kažkas negali nuspręsti, ką nori žaisti toliau, ... Dėl šios priežasties Aloyzas sugalvojo naują žaidimą. Ji parengė daugybę kortų su paveiksliukais porų. Mokykloje yra N suolų, tad Aloyzas išsirenka N porų kortelių iš savo atsargų (paveiksliukai kortelėse sunumeruoti nuo 1 iki N) ir ant kiekvieno stalo padeda po dvi korteles. Viena iš šių kortelių padedama paveiksliuku į viršų, o kita - paveiksliuku žemyn.

Žaidimo pradžioje K vaikų (K\\leqN) susėda prie suolų taip, kad prie kiekvieno suolo būtų ne daugiau kaip vienas vaikas. Per pirmąją žaidimo minutę kiekvienas vaikas pažiūri į užverstą kortelę ir pereina prie to suolo, kurio atverstos kortelės paveiksliukas sutampa su tuo, ką vaikas pamatė užverstoje kortelėje. Vaikai kartoja tuos pačius veiksmus ir kiekvieną kitą minutę.

Geriausia šio žaidimo dalis yra ta, kad vaikai gali žaisti iki pat jų tėvų atvykimo. Taip pat, jei kai kuriuos vaikus jau pasiima tėvai, likę vaikai vis tiek gali tęsti žaidimą!

Yra tik viena problema: Aloyzui yra sunku nurodyti tėvams suolą, kuriame bus jų vaikas bet kuriuo laiko momentu. Jis sutiko duoti jums pradinį vaikų susėdimo planą bei informaciją apie visas padėtas korteles (net ir tas, kurios yra užverstos), kad tik padėtumėte jai greitai atsakyti į tėvų užklausas.

Pradiniai duomenys

Pirmoje eilutėje pateikti du sveikieji skaičiai N ir K (1\\leqK\\leqN\\leq10^5).

Toliau seka N eilučių. i-ojoje iš jų pateikti du sveikieji skaičiai a_i ir b_i, apibūdinantys korteles, padėtas ant i-ojo suolo. a_i yra atverstos kortelės paveiksliuko numeris, o b_i - užverstos kortelės paveiksliuko numeris (1\\leqa_i,b_i\\leqN).

Toliau seka K eilučių. i-ojoje iš jų pateikti du sveikieji skaičiai c_i bei t_i, apibūdinantys i-ąją tėvų užklausą. c_i yra suolo, kuriame iš pradžių sėdėjo vaikas, numeris, o t_i - kiek minučių po žaidimo pradžios pateikta užklausa (1\\leqc_i\\leqN,1\\leqt_i\\leq10^9).

Rezultatai

Jūsų programa turi išvesti K sveikųjų skaičių, po vieną eilutėje. i-asis iš šių skaičių nurodo, prie kurio suolo sėdės i-asis vaikas, kai atvyks jo tėvai (vaikai numeruojami ta tvarka, kuria jie pasirodė įvestyje).

Pavyzdžiai

Pradiniai duomenys Rezultatai 
6 4
1 2
2 3
3 1
5 4
4 5
6 6
1 10
3 3
4 101
6 1000
 
2
3
5
6