Se dau două numere naturale N și M. Se consideră un șir de numere de lungime N indexat de la 0 căruia trebuie să i se atribuie valori astfel încât să se respecte M restricții de forma:

0 i val1 val2 - elementul i poate avea doar valoarea val1 sau val2
1 i j val – fix unul dintre elementele de pe pozițiile i și j trebuie să aibă valoarea val
2 i j – elementele de pe pozițiile i și j trebuie să aibă valori diferite
3 i j – elementele de pe pozițiile i și j trebuie să aibă aceeași valoare

Cerința

Determinați o atribuire de valori asupra șirului astfel încât acesta să respecte cele M restricții.

Date de intrare

Pe prima linie din fișierul valori.in se află două numere naturale N și M. Pe a doua linie din fișierul de intrare se află cele M restricții. Primele N restricții (N + 1 linii) reprezintă restricții de tipul 0. Următoarele M – N linii sunt restricții de tipul 1, 2, sau 3.

Date de ieșire

Fișierul de ieșire valori.out va conține valorile atribuite fiecărui element din șirul de lungime N.

Restricții și precizări

• 1 ≤ N ≤ 10.000
• 1 ≤ M ≤ 40.000
• Toate valorile din input se vor încadra be 32 de biti.
• Se poate afișa orice soluție corectă.
• Se garantează ca există cel puțin o soluție.

Exemplu:

valori.in

6 10
0 0 1 2
0 1 1 0
0 2 3 2
0 3 2 3
0 4 1 0
0 5 1 3
1 2 3 2
2 0 4
3 1 0
3 5 1

valori.out

1 1 3 2 0 1