スパイ 2 (Spy 2)

JOI 国には N 人の議員がおり，1 から N までの番号がつけられている．JOI 国の大臣であるあなたは，議員の中にいるスパイを探し出そうとしている．あなたは各議員 i (1 ≦ i ≦ N) について次のような情報を得た．

• Ti = 1 のとき，議員 i はスパイである．
• Ti = 2 のとき，議員 i はスパイではない．
• Ti = 3 のとき，議員 i がスパイであるかどうかは不明である．

更に聞き取り調査を行った結果，新たに M 個の情報を得ることができた．j 番目の聞き取り調査の情報 (1 ≦ j ≦ M) は，議員 Aj (1 ≦ Aj ≦ N) が「議員 Bj (1 ≦ Bj ≦ N) はスパイであり，かつ議員 Cj (1 ≦ Cj ≦ N) はスパイでない」と証言したというものである．

ただし，議員 Aj がスパイであれば，j 番目の聞き取り調査の情報における証言は事実とは異なる．すなわち，もし議員 Aj がスパイであれば，「議員 Bj はスパイである」「議員 Cj はスパイでない」のうち，少なくとも一方は事実ではない．一方で，議員 Aj がスパイでないとき，j 番目の聞き取り調査の情報における証言は事実かもしれないし，そうでないかもしれない．

各議員の情報と，聞き取り調査の結果が与えられるので，それら N + M 個の情報が矛盾しているかを判定し，矛盾していないなら，それぞれの議員がスパイかどうかを求めるプログラムを作成せよ．N + M 個の情報と合致する答えが複数存在する場合は，そのうちどれを出力してもよい．

入力は以下の形式で標準入力から与えられる．

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

標準出力に出力せよ．

与えられた情報が矛盾している場合，-1 を 1 行で出力せよ．

そうでない場合，出力は N 行からなる．i 行目 (1 ≦ i ≦ N) には議員 i がスパイである場合 1 を，議員 i がスパイでない場合 2 を出力せよ．N + M 個の情報と合致する答えが複数存在する場合，そのうちどれを出力してもよい．

• 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)．