Условие задачи

В стране 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$ — единственный верный ответ. Обратите внимание, что показание депутата, не являющегося шпионом, может быть как истинным, так и ложным.