레이팅 미적용JOI 国には N 人の議員がおり, 1 から N までの番号がつけられている.JOI 国の大臣であるあなたは,議員の中にいるスパイを探し出そうとしている.あなたは各議員 i ( \(1 \le i \le N\) ) について次のような情報を得た.
T i = 1 のとき,議員 i はスパイである.
T i = 2 のとき,議員 i はスパイではない.
T i = 3 のとき,議員 i がスパイであるかどうかは不明である.
更に聞き取り調査を行った結果,新たに M 個の情報を得ることができた. j 番目の聞き取り調査の情報 ( \(1 \le j \le M\) ) は,議員 A j ( 1 ≦ A j ≦ N ) が「議員 B j ( 1 ≦ B j ≦ N ) はスパイであり,かつ議員 C j ( 1 ≦ C j ≦ N ) はスパイでない」と証言したというものである.
ただし,議員 A j がスパイであれば, j 番目の聞き取り調査の情報における証言は事実とは異なる.すなわち,もし議員 A j がスパイであれば,「議員 B j はスパイである」「議員 C j はスパイでない」のうち,少なくとも一方は事実ではない.一方で,議員 A j がスパイでないとき, j 番目の聞き取り調査の情報における証言は事実かもしれないし,そうでないかもしれない.
各議員の情報と,聞き取り調査の結果が与えられるので,それら N + M 個の情報が矛盾しているかを判定し,矛盾していないなら,それぞれの議員がスパイかどうかを求めるプログラムを作成せよ. N + M 個の情報と合致する答えが複数存在する場合は,そのうちどれを出力してもよい.
1 ≦ N ≦ 300 000 .
1 ≦ M ≦ 300 000 .
1 ≦ T i ≦ 3 ( \(1 \le i \le N\) ).
1 ≦ A j ≦ N ( \(1 \le j \le M\) ).
1 ≦ B j ≦ N ( \(1 \le j \le M\) ).
1 ≦ C j ≦ N ( \(1 \le j \le M\) ).
A j ≠ B j ( \(1 \le j \le M\) ).
A j ≠ C j ( \(1 \le j \le M\) ).
B j ≠ C j ( \(1 \le j \le M\) ).
( 7 点) \(N \le 16\) , \(M \le 100\) .
( 38 点) N ≦ 3 000 , M ≦ 3 000 .
( 55 点) 追加の制約はない.
入力は以下の形式で標準入力から与えられる.
N M
T 1 T 2 ... T N
A 1 B 1 C 1
A 2 B 2 C 2
:
A M B M C M
標準出力に出力せよ.
与えられた情報が矛盾している場合, -1 を 1 行で出力せよ.
そうでない場合,出力は N 行からなる. i 行目 ( \(1 \le i \le N\) ) には議員 i がスパイである場合 1 を,議員 i がスパイでない場合 2 を出力せよ. N + M 個の情報と合致する答えが複数存在する場合,そのうちどれを出力してもよい.
4 1
1 3 2 3
1 2 3
1
2
2
1
4 2
2 1 3 1
4 3 1
2 4 3
-1
3 2
1 2 2
2 1 3
2 3 1
1
2
2