Enunciado del problema

En el país JOI hay $N$ parlamentarios numerados del $1$ al $N$. Como ministro del país JOI, estás intentando descubrir a los espías entre los parlamentarios. Para cada parlamentario $i$ ($1 \le i \le N$), obtuviste la siguiente información:

• Cuando $T_{i} = 1$, el parlamentario $i$ es un espía.
• Cuando $T_{i} = 2$, el parlamentario $i$ no es un espía.
• Cuando $T_{i} = 3$, se desconoce si el parlamentario $i$ es un espía o no.

Además, como resultado de los interrogatorios realizados, pudiste obtener $M$ nuevas informaciones. La $j$-ésima información de los interrogatorios ($1 \le j \le M$) consiste en que el parlamentario $A_{j}$ ($1 \le A_{j} \le N$) testificó que «el parlamentario $B_{j}$ ($1 \le B_{j} \le N$) es un espía, y el parlamentario $C_{j}$ ($1 \le C_{j} \le N$) no es un espía».

Sin embargo, si el parlamentario $A_{j}$ es un espía, el testimonio en la $j$-ésima información de los interrogatorios no se corresponde con los hechos. Es decir, si el parlamentario $A_{j}$ es un espía, al menos una de las afirmaciones «el parlamentario $B_{j}$ es un espía» y «el parlamentario $C_{j}$ no es un espía» no es cierta. Por otro lado, cuando el parlamentario $A_{j}$ no es un espía, el testimonio en la $j$-ésima información de los interrogatorios puede ser cierto o no.

Dada la información sobre cada parlamentario y los resultados de los interrogatorios, escribe un programa para determinar si estas $N + M$ informaciones son contradictorias y, de no serlo, hallar para cada parlamentario si es un espía o no. Si existen múltiples respuestas compatibles con las $N + M$ informaciones, puedes imprimir cualquiera de ellas.

Restricciones

• $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$).

Subtareas

1. ($7$ puntos) $N \le 16$, $M \le 100$.
2. ($38$ puntos) $N \le 3\,000$, $M \le 3\,000$.
3. ($55$ puntos) No hay restricciones adicionales.

Entrada

La entrada se proporciona desde la entrada estándar en el siguiente 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}$

Salida

Imprime en la salida estándar.

Si la información dada es contradictoria, imprime -1 en $1$ línea.

En caso contrario, la salida consta de $N$ líneas. En la $i$-ésima línea ($1 \le i \le N$), imprime $1$ si el parlamentario $i$ es un espía, o $2$ si el parlamentario $i$ no es un espía. Si existen múltiples respuestas compatibles con las $N + M$ informaciones, puedes imprimir cualquiera de ellas.

Ejemplos

Entrada de ejemplo 1

4 1
1 3 2 3
1 2 3

Salida de ejemplo 1

1
2
2
1

En la Salida de ejemplo $1$, el parlamentario $1$ es un espía, y el testimonio de que «el parlamentario $2$ es un espía, y el parlamentario $3$ no es un espía» es contrario a los hechos porque el parlamentario $2$ no es un espía. Por lo tanto, la Salida de ejemplo $1$ concuerda con la información dada y es correcta.

Además de esta, la respuesta en la que solo el parlamentario $1$ es un espía y los demás parlamentarios no son espías también es correcta.

Entrada de ejemplo 2

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

Salida de ejemplo 2

-1

Si el parlamentario $3$ fuera un espía, no concordaría con la $1$-ª información de los interrogatorios. Si el parlamentario $3$ no fuera un espía, no concordaría con la $2$-ª información de los interrogatorios. Como la información es contradictoria, se imprime -1.

Entrada de ejemplo 3

3 2
1 2 2
2 1 3
2 3 1

Salida de ejemplo 3

1
2
2

En la Entrada de ejemplo $3$, para todos los parlamentarios se da la información de si son espías o no. Como estos datos también concuerdan con la información de los interrogatorios, la Salida de ejemplo $3$ es la única respuesta correcta. Ten en cuenta que el testimonio de un parlamentario que no es espía puede ser cierto o no.