Problem Statement

In JOI Country, there are $N$ parliament members numbered from $1$ to $N$. As a minister of JOI Country, you are trying to find spies among the members. For each member $i$ ($1 \le i \le N$), you obtained the following information:

• When $T_{i} = 1$, member $i$ is a spy.
• When $T_{i} = 2$, member $i$ is not a spy.
• When $T_{i} = 3$, whether member $i$ is a spy or not is unknown.

Furthermore, as a result of interviews, you obtained $M$ new pieces of information. The $j$-th piece of interview information ($1 \le j \le M$) is that member $A_{j}$ ($1 \le A_{j} \le N$) testified that "member $B_{j}$ ($1 \le B_{j} \le N$) is a spy, and member $C_{j}$ ($1 \le C_{j} \le N$) is not a spy".

However, if member $A_{j}$ is a spy, the testimony in the $j$-th piece of interview information is contrary to the facts. That is, if member $A_{j}$ is a spy, at least one of "member $B_{j}$ is a spy" and "member $C_{j}$ is not a spy" is not true. On the other hand, if member $A_{j}$ is not a spy, the testimony in the $j$-th piece of interview information may or may not be true.

Given the information on each member and the interview results, write a program to determine whether these $N + M$ pieces of information are contradictory, and if not, find whether each member is a spy or not. If there are multiple answers consistent with the $N + M$ pieces of information, you may output any of them.

Constraints

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

Subtasks

1. ($7$ points) $N \le 16$, $M \le 100$.
2. ($38$ points) $N \le 3\,000$, $M \le 3\,000$.
3. ($55$ points) No additional constraints.

Input

The input is given from standard input in the following format:

$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

Print to standard output.

If the given information is contradictory, print -1 in $1$ line.

Otherwise, the output consists of $N$ lines. On the $i$-th line ($1 \le i \le N$), print $1$ if member $i$ is a spy, or $2$ if member $i$ is not a spy. If there are multiple answers consistent with the $N + M$ pieces of information, you may output any of them.

Sample

Sample Input 1

4 1
1 3 2 3
1 2 3

Sample Output 1

1
2
2
1

In Sample Output $1$, member $1$ is a spy, and the testimony that "member $2$ is a spy, and member $3$ is not a spy" is contrary to the facts because member $2$ is not a spy. Therefore, Sample Output $1$ is consistent with the given information and is correct.

Besides this, the answer in which only member $1$ is a spy and the other members are not spies is also correct.

Sample Input 2

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

Sample Output 2

-1

If member $3$ is a spy, it contradicts the $1$-st piece of interview information. If member $3$ is not a spy, it contradicts the $2$-nd piece of interview information. Since the information is contradictory, print -1.

Sample Input 3

3 2
1 2 2
2 1 3
2 3 1

Sample Output 3

1
2
2

In Sample Input $3$, information on whether each member is a spy or not is given for all members. Since these are also consistent with the interview information, Sample Output $3$ is the unique correct answer. Note that the testimony of a member who is not a spy may or may not be true.