Candidati

Pe planeta Utopia urmează să se organizeze alegeri. Fiecare dintre cele $N$ partide va trebui să-și aleagă un singur candidat dintre $M$ politicieni și bineînțeles un politician poate candida pentru cel mult un partid.

Pentru fiecare partid cunoaștem intervalele disjuncte de timp când au fost la guvernare, iar pentru fiecare politician cunoaștem intervalele de timp în care a colaborat cu diverse asociații non-profit la care a făcut voluntariat. Se poate întâmpla ca un politician să facă voluntariat simultan în mai locuri.

Preferința unui partid $i$ pentru un politician $j$ se obține prin însumarea timpului total în care politicianul $j$ a făcut voluntariat, în cel puțin un loc, în perioadele în care partidul $i$ a fost la guvernare. Cu cât acest număr este mai mare, cu atât partidul $i$ preferă mai mult politicianul $j$.

Preferința unui politician $j$ pentru un partid $i$ se obține în felul următor:

• Pentru fiecare partid $i$ calculăm numărul $p_i$ de puncte de putere al partidului ca fiind numărul minim de intervale de voluntariat ale tuturor politicienilor cu care se pot acoperi toate intervalele în care partidul $i$ s-a aflat la guvernare, sau 0 dacă acest lucru este imposibil.
• Notăm cu $t_0$ primul moment de timp și cu $t_1$ ultimul moment de timp când politicianul $j$ a făcut voluntariat. Definim $q_j$ ca fiind numărul de perioade din intervalul $[t_0, t_1]$ când politicianul nu a făcut voluntariat.
• Pentru un partid $i$ și politician $j$, definim preferința politicianului pentru partidul $i$ ca fiind numărul de moduri de a distribui cele $p_i$ puncte de putere ale partidului în cele $q_j$ intervale în care nu a făcut voluntariat (modulo $1 \ 000 \ 000 \ 007$). Fiecărui interval i se poate distribui un număr natural de puncte, eventual $0$. Dacă cel puțin unul dintre $p_i = 0$ și $q_j = 0$ preferința este $1$. Cu cât acest număr este mai mare, cu atât politicianul $j$ preferă partidul $i$ mai mult.

Fie $c_i$ candidatul ales de partidul $i$ pentru alegeri ($1 \leq c_i \leq M$). Alegerile se consideră echilibrate dacă nu există două partide $i$ și $j$ ($1 \leq i, j \leq N, i \neq j$) unde partidul $i$ preferă politicianul $c_j$ mai mult decât pe politicianul $c_i$, iar politicianul $c_j$ preferă partidul $i$ mai mult decât partidul $j$.

Cerințe

Sunt trei cerințe, iar cerința de rezolvat este dată de $C \in \{1, 2, 3\}$.

• $\bm{C = 1}$: Dându-se partidul $x$, determinați preferințele sale pentru fiecare dintre cei $M$ politicieni.
• $\bm{C = 2}$: Dându-se politicianul $y$, determinați preferințele sale pentru fiecare dintre cele $N$ partide.
• $\bm{C = 3}$: Determinați suma tuturor preferințelor partidelor (modulo $1 \ 000 \ 000 \ 007$), suma tuturor preferințelor politicienilor (modulo $1 \ 000 \ 000 \ 007$) și o listă de candidați, în așa fel încât alegerile să fie echilibrate, dacă acest lucru este posibil.

Date de intrare

Pe prima linie se află $C$, numărul cerinței, urmat de valoarea $x$ pentru cerința $1$ sau de valoarea $y$ pentru cerința $2$.

Pe a doua linie se află $N$, numărul partidelor. Urmează în ordine descrierea intervalelor de timp când partidele au fost la guvernare. O descriere de acest fel începe cu valoarea $K$, reprezentând numărul intervalelor, urmată de $K$ linii, care conțin câte două numere întregi $a$ și $b$, începutul și sfârșitul intervalului.
Pe următorul rând se află $M$, numărul politicienilor. Descrierea lor are același format ca în cazul partidelor.

Date de ieșire

• $\bm{C = 1}$: Se vor afișa $M$ linii. Linia $j$ reprezintă preferințele partidului $x$ pentru politicianul $j$.
• $\bm{C = 2}$: Se vor afișa $N$ linii. Linia $i$ reprezintă preferințele politicianului $y$ pentru partidul $i$.
• $\bm{C = 3}$: Pe prima linie se va afișa suma tuturor preferințelor partidelor (modulo $1 \ 000 \ 000 \ 007$). Pe a doua linie se va afișa suma tuturor preferințelor politicienilor (modulo $1 \ 000 \ 000 \ 007$). Dacă nu se pot organiza alegeri echilibrate, pe următoarea linie se va afișa -1. În caz contrar se vor afișa încă $N$ linii. Cea de-a $i$-a linie dintre acestea reprezintă candidatul $c_i$ trimis la alegeri de partidul $i$. Dacă există mai multe soluții, se poate afișa oricare dintre ele.

Restricții și precizări

• $1 \leq N \leq M \leq 1 \ 000$;
• $1 \leq K \leq 100$;
• $1 \leq x \leq N$;
• $1 \leq y \leq M$;
• $0 \leq a \leq b \leq 10^{18}$;
• La cerința $3$ punctajul aferent fiecărui test se acordă astfel: $20\%$ dacă prima linie a fișierului de ieșire este corectă, $20\%$ dacă a doua linie a fișierului de ieșire este corectă și $60\%$ dacă restul liniilor din fișier sunt corecte.
• Intervalele în care un anumit partid a fost la guvernare sunt disjuncte.

Exemplul 1

candidati.in

1 2
2
1
1 10
2
8 10
2 6
3
1
1 10
3
9 10
1 2
5 6
2
6 8
7 7

candidati.out

8
5
2

Explicație

Partidul 2 a fost la guvernare în perioadele $[2, 6]$ respectiv $[8, 10]$.

Primul politician a făcut voluntariat în perioada $[1, 10]$, unitățile de timp comune cu partidul $2$ fiind: $2, 3, 4, 5, 6, 8, 9, 10$, în total $8$ unități de timp.

Al doilea politician a făcut voluntariat în perioadele $[1, 2]$, $[5, 6]$ și $[9, 10]$, unitățile de timp comune cu partidul $2$ fiind: $2, 5, 6, 9, 10$, în total $5$ unități de timp.

Al treilea politician a făcut voluntariat în perioada $[6, 8]$ și simultan în perioada $[7, 7]$ unitățile de timp comune cu partidul $2$ fiind $6$ și $8$, în total $2$ unități de timp.

Exemplul 2

candidati.in

2 2
2
1
1 10
2
8 10
2 6
3
2
2 5
8 9
3
9 10
1 2
5 7
2
6 8
7 7

candidati.out

7
5

Explicație

Politicianul $2$ a făcut voluntariat în perioadele $[1, 2]$, $[5, 7]$, respectiv $[9, 10]$, deci a început să facă voluntariat pentru prima oară în momentul $t_0 = 1$ și a încetat să facă voluntariat ultima oară în momentul $t_1 = 10$. În perioada $[t_0, t_1]$ au fost $q_2 = 2$ perioade în care n-a luat parte la niciun voluntariat, respectiv $[3, 4]$ și $[8, 8]$.

Partidul $1$ a fost la guvernare în perioada $[1, 10]$, perioadă ce se poate acoperi cu minim $p_1 = 6$ intervale dintre cele asociate politicienilor: $[1, 2]$, $[2, 5]$, $[5, 7]$, $[6, 8]$, $[8, 9]$ și $[9, 10]$. În cele $q_2 = 2$ perioade se pot distribui $p_1 = 6$ puncte de putere ale partidului în $7$ moduri: în prima perioadă se pot distribui $0, 1, 2, 3, 4, 5$, sau $6$ puncte, iar în a doua perioadă restul.

Partidul $2$ a fost la guvernare în perioadele $[2, 6]$ și $[8, 10]$, perioade ce se pot acoperi cu minim $p_2 = 4$ intervale dintre cele asociate politicienilor: $[2, 5]$, $[5, 7]$, $[8, 9]$ și $[9, 10]$. În cele $q_2 = 2$ perioade se pot distribui cele $p_2 = 4$ puncte în $5$ moduri.

Exemplul 3

candidati.in

3
2
1
1 10
2
8 10
2 6
3
2
2 5
8 9
3
9 10
1 2
5 6
2
6 8
7 7

candidati.out

28
16
2
1

Explicație

Suma tuturor preferințelor partidelor este $28$.

Suma tuturor preferințelor politicienilor este $16$.

Pentru partidul $1$ candidează politicianul $2$, iar pentru partidul $2$ candidează politicianul $1$, lista de candidați fiind echilibrată. Dacă pentru partidul $1$ ar fi candidat politicianul $3$ și pentru partidul $2$ ar fi candidat politicianul $2$, lista candidaților n-ar mai fi fost echilibrată, pentru că politicianul $2$ preferă mai mult partidul $1$ (preferința $7$) decât partidul $2$ (preferința $5$) și partidul $1$ preferă mai mult politicianul $2$ (preferința $6$) decât politicianul $3$ (preferința $3$).