Zombi

Miki și Livia sunt două vrăjitoare care vor să rezolve o dispută. Natural, ele vor conjura armate de zombi care se vor bate între ele în locul lor. Fiecare zombi $z$ are două atribute: un nivel de atac $a_z$ și un nivel de rezistență $r_z$.

Cele două tocmai au inițiat prima rundă, iar Livia a conjurat $N$ zombi pe care i-a trimis la atac. Miki a conjurat la rândul ei $M$ zombi pe care îi va folosi pentru a bloca atacul Liviei. Pentru fiecare dintre zombii pe care i-a conjurat, Miki poate alege să-l trimită să blocheze unul dintre zombii neblocați ai Liviei. Ea poate lăsa unii dintre zombii Liviei neblocați și poate să nu trimită toți cei $M$ zombi la luptă.

Apoi, zombii se bat între ei: fiecare zombi atacator blocat și zombiul care îl blochează se bat individual, lansând atacuri simultane. Un zombi $x$ va fi eliminat de atacul unui zombi $y$ dacă $r_x < a_y$. În funcție de nivelurile de atac și rezistență ale zombiilor dintr-o luptă, zero, unul sau amândoi vor fi eliminați în urma luptei.

După ce luptele sunt încheiate, Livia înscrie un număr de puncte egal cu suma nivelurilor de atac ale zombiilor săi neblocați. Zombii atacatori blocați, zombii care blochează și zombii nefolosiți de Miki pentru a bloca nu înscriu puncte pentru nicio vrăjitoare.

Apoi, Miki și Livia își recheamă zombii neeliminați și bătălia continuă... însă pe noi ne interesează doar prima rundă.

După ce vede zombii trimiși de Livia la atac, Miki se gândește să trimită strategic zombii săi să blocheze pentru a îndeplini unul dintre următoarele obiective în prima rundă de atac:

• Obiectivul 1: Livia înscrie cât mai puține puncte.
• Obiectivul 2: Livia înscrie cât mai puține puncte, fără ca vreunul dintre zombii lui Miki să fie eliminat.
• Obiectivul 3: Livia înscrie cât mai puține puncte, preferându-se ca numărul de zombii eliminați ai lui Miki pentru a atinge acest scop să fie minim.
• Obiectivul 4: Miki elimină cât mai mulți dintre zombii Liviei.
• Obiectivul 5: Miki elimină cât mai mulți dintre zombii Liviei, fără ca vreunul dintre zombii lui Miki să fie eliminat.

Scopul vostru este să o ajutați pe Miki să blocheze zombii Liviei corespunzător pentru a atinge obiectivul dorit.

Date de intrare

Pe prima linie se vor afla trei întregi $O$, $N$ și $M$, reprezentând obiectivul dorit de Miki, numărul de zombii trimiși de Livia la atac, respectiv numărul de zombii pe care Miki îi are la dispoziție.

Următoarele $N$ linii conțin perechi de întregi $a$ și $r$; a $i$-a dintre aceste perechi reprezintă nivelurile de atac, respectiv de rezistență ale al $i$-lea zombi trimis de Livia la atac.

Următoarele $M$ linii conțin perechi de întregi $a$ și $r$; a $i$-a dintre aceste perechi reprezintă nivelurile de atac, respectiv de rezistență ale al $i$-lea zombi aflat la dispoziția lui Miki.

Date de ieșire

Afișați o singură linie conținând $M$ numere separate prin câte un spațiu, $x_1, x_2, \dots, x_M$, reprezentând, pentru fiecare $i$ de la $1$ la $M$, faptul că Miki va folosi zombiul $i$ pentru a bloca zombiul $x_i$ trimis de Livia, respectiv că Miki nu va folosi zombiul $i$ pentru a bloca niciun zombi, dacă $x_i$ este $0$. Dacă există mai multe soluții corecte, o puteți afișa pe oricare dintre ele.

Restricții și precizări

• $1 \leq N, M \leq 500\ 000$
• $1 \leq O \leq 5$
• Nivelurile de atac, respectiv rezistență ale tuturor zombiilor sunt cuprinse între $1$ și $2\ 000\ 000\ 000$ inclusiv.
• Nu există doi zombi diferiți cu niveluri de atac egale.
• Nu există doi zombi diferiți cu niveluri de rezistență egale.
• Pot exista doi zombi diferiți pentru care nivelul de atac al unuia este egal cu nivelul de rezistență al celuilalt.

Exemplu 1

stdin

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

stdout

1 2

Explicație

Miki vrea să se apere astfel încât Livia să înscrie cât mai puține puncte.

Pentru a face asta, ea trimite zombiul $1$ al său să blocheze zombiul $1$ al Liviei, și zombiul $2$ al său să blocheze zombiul $2$ al Liviei.

Zombii $3$ și $4$ ai Liviei sunt neblocați și înscriu în total $3 + 2 = 5$ puncte, care este minimul posibil.

Exemplu 2

stdin

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

stdout

1 2 4 3

Explicație

Miki vrea să se apere astfel încât Livia să înscrie cât mai puține puncte, și niciunul dintre zombii lui Miki să nu fie eliminat.

Miki blochează astfel:
Zombiul $1$ al său blochează zombiul $1$ al Liviei,
Zombiul $2$ al său blochează zombiul $2$ al Liviei,
Zombiul $3$ al său blochează zombiul $4$ al Liviei,
Zombiul $4$ al său blochează zombiul $3$ al Liviei.

Fiecare zombi care blochează are un nivel de rezistență mai mare decât nivelul de atac al zombiului pe care l-a blocat, astfel că niciunul dintre zombii lui Miki nu este eliminat.

Livia înscrie $0$ puncte - toți zombii săi sunt blocați.

Exemplu 3

stdin

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

stdout

2 1 3

Explicație

Miki vrea să se apere astfel încât Livia să înscrie cât mai puține puncte, și numărul de zombii ai lui Miki eliminați în urma luptelor pentru a atinge acest obiectiv să fie minim.

Miki blochează astfel:
Zombiul $1$ al său blochează zombiul $2$ al Liviei,
Zombiul $2$ al său blochează zombiul $1$ al Liviei,
Zombiul $3$ al său blochează zombiul $3$ al Liviei.

Blocând astfel, Livia înscrie $2$ puncte și niciunul dintre zombii lui Miki nu este eliminat; există și alte metode de a bloca pentru ca Livia să înscrie $2$ puncte, dar acelea nu sunt răspunsuri valide deoarece în urma lor cel puțin un zombi de-al lui Miki este eliminat.

Exemplu 4

stdin

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

stdout

3 2 0

Explicație

Miki vrea să se apere astfel încât să elimine cât mai mulți dintre zombii Liviei.

Ea va elimina zombiul $3$ al Liviei cu zombiul $1$ al său, și zombiul $2$ al Liviei cu zombiul $2$ al său; nu există o modalitate de a bloca ce elimină mai mulți zombi ai Liviei.

Exemplu 5

stdin

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

stdout

3 2 0

Explicație

Miki vrea să se apere astfel încât să elimine cât mai mulți dintre zombii Liviei, și niciunul dintre zombii lui Miki să nu fie eliminat.

Ea va elimina zombiul $3$ al Liviei cu zombiul $1$ al său, și zombiul $2$ al Liviei cu zombiul $2$ al său; niciunul dintre zombii lui Miki nu moare astfel. Nu există o altă metodă de a bloca astfel încât Miki să elimine mai mulți zombi de-ai Liviei, și niciun zombi de-al lui Miki să nu fie eliminat.