Testo del problema

Nel paese di JOI ci sono $N$ parlamentari, numerati da $1$ a $N$. Come ministro del paese di JOI, stai cercando di individuare le spie tra i parlamentari. Per ciascun parlamentare $i$ ($1 \le i \le N$), hai ottenuto le seguenti informazioni:

• Quando $T_{i} = 1$, il parlamentare $i$ è una spia.
• Quando $T_{i} = 2$, il parlamentare $i$ non è una spia.
• Quando $T_{i} = 3$, non è noto se il parlamentare $i$ sia una spia oppure no.

Inoltre, in seguito a degli interrogatori, hai ottenuto $M$ nuove informazioni. La $j$-esima informazione degli interrogatori ($1 \le j \le M$) afferma che il parlamentare $A_{j}$ ($1 \le A_{j} \le N$) ha testimoniato che «il parlamentare $B_{j}$ ($1 \le B_{j} \le N$) è una spia, e il parlamentare $C_{j}$ ($1 \le C_{j} \le N$) non è una spia».

Tuttavia, se il parlamentare $A_{j}$ è una spia, la testimonianza contenuta nella $j$-esima informazione degli interrogatori è contraria ai fatti. Cioè, se il parlamentare $A_{j}$ è una spia, almeno una tra le affermazioni «il parlamentare $B_{j}$ è una spia» e «il parlamentare $C_{j}$ non è una spia» non è vera. D'altra parte, quando il parlamentare $A_{j}$ non è una spia, la testimonianza nella $j$-esima informazione degli interrogatori può essere vera oppure no.

Date le informazioni su ciascun parlamentare e i risultati degli interrogatori, scrivi un programma per determinare se queste $N + M$ informazioni sono contraddittorie e, in caso contrario, stabilire per ciascun parlamentare se è una spia oppure no. Se esistono più risposte coerenti con le $N + M$ informazioni, puoi stamparne una qualsiasi.

Vincoli

• $1 \le N \le 300\,000$.
• $1 \le M \le 300\,000$.
• $1 \le T_{i} \le 3$ ($1 \le i \le N$).
• $1 \le A_{j} \le N$ ($1 \le j \le M$).
• $1 \le B_{j} \le N$ ($1 \le j \le M$).
• $1 \le C_{j} \le N$ ($1 \le j \le M$).
• $A_{j} \ne B_{j}$ ($1 \le j \le M$).
• $A_{j} \ne C_{j}$ ($1 \le j \le M$).
• $B_{j} \ne C_{j}$ ($1 \le j \le M$).

Sottoproblemi

1. ($7$ punti) $N \le 16$, $M \le 100$.
2. ($38$ punti) $N \le 3\,000$, $M \le 3\,000$.
3. ($55$ punti) Nessun vincolo aggiuntivo.

Input

L'input è fornito dallo standard input nel seguente formato:

$N$ $M$
$T_{1}$ $T_{2}$ $\dots$ $T_{N}$
$A_{1}$ $B_{1}$ $C_{1}$
$A_{2}$ $B_{2}$ $C_{2}$
$:$
$A_{M}$ $B_{M}$ $C_{M}$

Output

Stampa sullo standard output.

Se le informazioni fornite sono contraddittorie, stampa -1 in $1$ riga.

Altrimenti, l'output è costituito da $N$ righe. Nella $i$-esima riga ($1 \le i \le N$), stampa $1$ se il parlamentare $i$ è una spia, oppure $2$ se il parlamentare $i$ non è una spia. Se esistono più risposte coerenti con le $N + M$ informazioni, puoi stamparne una qualsiasi.

Esempi

Input di esempio 1

4 1
1 3 2 3
1 2 3

Output di esempio 1

1
2
2
1

Nell'Output di esempio $1$, il parlamentare $1$ è una spia, e la testimonianza «il parlamentare $2$ è una spia, e il parlamentare $3$ non è una spia» è contraria ai fatti poiché il parlamentare $2$ non è una spia. Pertanto, l'Output di esempio $1$ è coerente con le informazioni fornite ed è corretto.

Oltre a questa, è corretta anche la risposta in cui solo il parlamentare $1$ è una spia e gli altri parlamentari non sono spie.

Input di esempio 2

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

Output di esempio 2

-1

Se il parlamentare $3$ fosse una spia, ciò non sarebbe coerente con la $1$-a informazione degli interrogatori. Se il parlamentare $3$ non fosse una spia, ciò non sarebbe coerente con la $2$-a informazione degli interrogatori. Poiché le informazioni sono contraddittorie, si stampa -1.

Input di esempio 3

3 2
1 2 2
2 1 3
2 3 1

Output di esempio 3

1
2
2

Nell'Input di esempio $3$, per tutti i parlamentari è data l'informazione se siano spie oppure no. Poiché queste informazioni sono coerenti anche con quelle degli interrogatori, l'Output di esempio $3$ è l'unica risposta corretta. Nota che la testimonianza di un parlamentare che non è una spia può essere vera oppure no.