Bomba

Enunț

Ai observat o bombă care stă să explodeze! Bomba are $N$ fire, numerotate de la $1$ la $N$. Pentru a o dezamorsa, trebuie să tai fiecare fir exact odată, într-un interval de $N$ secunde (secundele $1, 2, \dots, N$). În fiecare secundă, trebuie să tai exact un fir.

Cerință

Din păcate, firele nu pot fi tăiate în orice ordine. Există anumite instrucțiuni tehnice pe care trebuie să le respecți pentru a nu declanșa explozia. Vei primi $M$ instrucțiuni de tipul $t, a, b$, unde:

• $t = 1$: Firul $a$ trebuie tăiat înainte de firul $b$.
• $t = 2$: Firul $a$ trebuie tăiat după firul $b$.
• $t = 3$: Firul $a$ trebuie tăiat cel mai devreme la secunda $b$ ($T_a \ge b$).
• $t = 4$: Firul $a$ trebuie tăiat cel mai târziu la secunda $b$ ($T_a \le b$).

Găsește o ordine în care tai cele $N$ fire astfel încât să dezamorsezi bomba!

Date de intrare

Pe prima linie a fișierului de intrare bomba.in se găsesc două numere întregi, $N$ (numărul de fire) și $M$ (numărul de instrucțiuni). Pe următoarele $M$ linii se găsesc instrucțiunile, sub forma a trei numere întregi $t, a, b$.

Date de ieșire

Pe prima linie a fișierului de ieșire bomba.out se va găsi o permutare a numerelor de la $1$ la $N$, reprezentând ordinea în care trebuie tăiate firele. Dacă există mai multe soluții, se poate afișa oricare. În cazul în care nu există nicio ordine care să respecte toate instrucțiunile, se va afișa mesajul Imposibil.

Restricții și precizări

• $1 \leq N \leq 200 \ 000$;
• $1 \leq M \leq 500 \ 000$;
• Se garantează că pentru toate testele, valorile de timp $v$ din instrucțiunile de tip 3 și 4 sunt în intervalul $[1, N]$.
• O ordine de tăiere este o permutare $P = (p_1, p_2, \dots, p_N)$, unde $p_i$ este firul tăiat la secunda $i$.
• $T_{p_i} = i$ (firul $p_i$ este tăiat la secunda $i$).

Subtask-uri și punctare

• Restricția „Fiecare fir apare în cel mult o instrucțiune de tip 1 sau 2” înseamnă că numărul total de apariții ale unui fir în toate instrucțiunile de tip 1 și 2 la un loc este de maximum 1. În schimb, un fir poate apărea de oricâte ori în instrucțiunile de tip 3 și 4.

Exemplul 1

bomba.in

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

bomba.out

5 1 2 4 3

Explicație

Ai 5 fire. Firul 1 trebuie tăiat înaintea lui 2, iar 2 înaintea lui 3. Firul 4 se taie minim la secunda 4, iar firul 5 maxim la secunda 2. O ordine validă este 5 1 2 4 3.

Exemplul 2

bomba.in

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

bomba.out

Imposibil

Explicație

Nu ai suficiente secunde la dispoziție pentru a tăia toate firele fără să încalci vreo regulă.