Spy 2

JOI has N members of parliament, numbered from 1 to N. As the minister of JOI, you are trying to find the spies among them. For each member i (1 ≦ i ≦ N), you have the following information.

• If Ti = 1, member i is a spy.
• If Ti = 2, member i is not a spy.
• If Ti = 3, it is unknown whether member i is a spy.

You also conducted interviews and obtained M more pieces of information. The j-th interview result (1 ≦ j ≦ M) says that member Aj (1 ≦ Aj ≦ N) testified that "member Bj (1 ≦ Bj ≦ N) is a spy, and member Cj (1 ≦ Cj ≦ N) is not a spy."

If member Aj is a spy, the testimony in the j-th interview is false. That is, if Aj is a spy, at least one of "Bj is a spy" and "Cj is not a spy" is false. If Aj is not a spy, the testimony may or may not be true.

Given the information about each member and the interview results, determine whether the N + M pieces of information contradict each other. If they are consistent, find for each member whether they are a spy. If several answers match all N + M pieces of information, you may output any of them.

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

N M
T1 T2 … TN
A1 B1 C1
A2 B2 C2
:
AM BM CM

If the information is contradictory, print -1 on a single line.

Otherwise, print N lines. On line i (1 ≦ i ≦ N), print 1 if member i is a spy, and 2 if member i is not a spy. If several answers match all N + M pieces of information, you may print any of them.

• 1 ≦ N ≦ 300 000.
• 1 ≦ M ≦ 300 000.
• 1 ≦ Ti ≦ 3 (1 ≦ i ≦ N).
• 1 ≦ Aj ≦ N (1 ≦ j ≦ M).
• 1 ≦ Bj ≦ N (1 ≦ j ≦ M).
• 1 ≦ Cj ≦ N (1 ≦ j ≦ M).
• Aj ≠ Bj (1 ≦ j ≦ M).
• Aj ≠ Cj (1 ≦ j ≦ M).
• Bj ≠ Cj (1 ≦ j ≦ M).