Умова задачі

У країні 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 \le A_{j} \le N$) дав свідчення: «депутат $B_{j}$ ($1 \le B_{j} \le N$) — шпигун, і водночас депутат $C_{j}$ ($1 \le C_{j} \le N$) не є шпигуном».

Однак, якщо депутат $A_{j}$ — шпигун, то свідчення в $j$-й відомості опитування суперечить дійсності. Іншими словами, якщо депутат $A_{j}$ — шпигун, то принаймні одне з тверджень «депутат $B_{j}$ — шпигун» та «депутат $C_{j}$ не є шпигуном» не відповідає дійсності. З іншого боку, коли депутат $A_{j}$ не є шпигуном, свідчення в $j$-й відомості опитування може як відповідати дійсності, так і не відповідати їй.

За заданою інформацією про кожного депутата та результатами опитувань напишіть програму, яка визначить, чи суперечать ці $N + M$ відомостей одна одній, і якщо ні, з'ясує для кожного депутата, чи є він шпигуном. Якщо існує кілька відповідей, що узгоджуються з $N + M$ відомостями, ви можете вивести будь-яку з них.

Обмеження

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

Підзадачі

1. ($7$ балів) $N \le 16$, $M \le 100$.
2. ($38$ балів) $N \le 3\,000$, $M \le 3\,000$.
3. ($55$ балів) Додаткових обмежень немає.

Вхідні дані

Вхідні дані подаються зі стандартного потоку вводу в такому форматі:

$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}$

Вихідні дані

Виведіть відповідь у стандартний потік виводу.

Якщо задані відомості суперечливі, виведіть -1 в $1$ рядку.

Інакше вихідні дані складаються з $N$ рядків. У $i$-му рядку ($1 \le i \le N$) виведіть $1$, якщо депутат $i$ — шпигун, і $2$, якщо депутат $i$ не є шпигуном. Якщо існує кілька відповідей, що узгоджуються з $N + M$ відомостями, дозволяється вивести будь-яку з них.

Приклади

Приклад вводу 1

4 1
1 3 2 3
1 2 3

Приклад виводу 1

1
2
2
1

У прикладі виводу $1$ депутат $1$ є шпигуном, а свідчення «депутат $2$ — шпигун, і водночас депутат $3$ не є шпигуном» суперечить дійсності, оскільки депутат $2$ не є шпигуном. Отже, приклад виводу $1$ узгоджується із заданою інформацією і є правильною відповіддю.

Крім цього, правильною також є відповідь, у якій лише депутат $1$ — шпигун, а решта депутатів не є шпигунами.

Приклад вводу 2

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

Приклад виводу 2

-1

Якщо припустити, що депутат $3$ — шпигун, це не узгоджується з $1$-ю відомістю опитування. Якщо припустити, що депутат $3$ не є шпигуном, це не узгоджується з $2$-ю відомістю опитування. Оскільки відомості суперечливі, виводиться -1.

Приклад вводу 3

3 2
1 2 2
2 1 3
2 3 1

Приклад виводу 3

1
2
2

У прикладі вводу $3$ для всіх депутатів задано інформацію про те, чи є вони шпигунами, чи ні. Ці дані також узгоджуються з відомостями опитування, тому приклад виводу $3$ є єдиною правильною відповіддю. Зверніть увагу, що свідчення депутата, який не є шпигуном, може бути як правдивим, так і неправдивим.