תיאור הבעיה

במדינת 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$ הוא התשובה הנכונה היחידה. שימו לב שעדותו של חבר פרלמנט שאינו מרגל עשויה להיות נכונה ועשויה להיות לא נכונה.