"Ә" қаласында банк тонау ықтималдығы туралы хабар түсті. Қала – жол айрықтарының жинағы, кейбір жол айрықтары екіжақты жолдармен жалғасады. Сонымен қатар, қалада қылмыстық аудандар (гетто) бар, олар арқылы ұры қаладан қашып құтылуы мүмкін.

Ұрлық жасалғаннан кейін, ұры сол аудандардын біріне жетуге тырысады. Қала полициясы ұрынын қашып кетуін болдырмай оны ұстауға тырысады. Кейбір жол айрықтарында шексіз полицейлер саны бар полиция бөлімшелері бар.

Полиция ұрлық қай жерде болатынын білмейді, сондықтан есептеулерге көмектесуіңізді сұрайды. Қаланың әр жол айрығы үшін: полицейлер ұрыны белсенді түрде ұстауға тырысса ұры қашып кете ала ма немесе оны ұстап алады ма екенін анықтау керек.

Ұры мен кез-келген полицейдің жылдамдығы сағатына \(1\) жолға тең деп есептейік (барлық жолдар бірдей ұзындықта). Егер ұры мен полицей бір уақытта бір жол айрығында болса, ұры ұсталды деп саналады. Егер ұры қылмыстық ауданға полициямен бір уақытта немесе кейінірек келсе, оны ұстап алады. Сондықтан, ұры қашып кетті деп саналады, егер жол айрығында болған кезде полицей болмаса, жолдағы әрбір жол айрығында шыққанға дейін.

Input

Алғашқы жолда \(n\) және \(m\) (\(1 \le n, m \le 10^5\)) деген екі сан бар – бұл жол айрықтарының және жолдардың саны.

Келесі \(m\) жолда \(a\) және \(b\) деген екі сан бар (\(1 \le a, b \le n\)), олар \(a\) және \(b\) нөмірлеріндегі жол айрықтары арасындағы жолды көрсетеді.

Келесі жолда полиция бөлімшелерінің орналасуы сипатталған: \(k_1\) саны (\(1 \le k_1 \le n\)), содан кейін \(k_1\) сан бар – олар полиция бөлімшелері орналасқан жол айрықтарының нөмірлері.

Келесі жолда ұрыға арналған шығулардың орналасуы сипатталған: \(k_2\) саны (\(1 \le k_2 \le n\)), содан кейін \(k_2\) сан бар – олар қылмыстық аудандардың жол айрықтарының нөмірлері.

Қылмыстық аудандар мен полиция бөлімшелері бір жол айрығында болуы мүмкін.

Output

Нөлдер мен бірліктерден тұратын \(n\) ұзындығы жолды басып шығарыңыз: \(i\)-ші позициясында \(1\) ұры қашып үлгерсе, әйтпесе \(0\).

Sample Input 1

7 7
1 3
2 7
3 7
3 5
5 7
5 6
2 6
1 1
1 2

Sample Output 1

0110111

Sample Input 2

7 7
1 3
2 7
3 7
3 5
5 7
5 6
2 6
2 5 4
1 2

Sample Output 2

0100011