Czy wierzysz w plotki?

W pewnym słynnym eksperymencie psychologicznym ludziom pokazywano dwie linie i proszono o wskazanie, która z nich jest dłuższa. W rzeczywistości, poza jedną osobą, pozostali uczestnicy byli podstawieni przez eksperymentatorów. Podstawione osoby twierdziły, że krótsza linia jest w rzeczywistości dłuższa. Gdy wszyscy wokół udzielali tej samej odpowiedzi, prawdziwy badany również twierdził, że krótsza linia jest dłuższa. Eksperyment ten pokazał, że ludzie są silnie podatni na wpływ otoczenia; podobnie jest z plotkami.

Plotka zaczyna się od pierwotnych nadawców. Może być ich wielu, a poza nimi nikt nie tworzy ani nie wierzy w plotkę sam z siebie.

Co minutę osoba wierząca w plotkę rozprzestrzenia ją jednocześnie na wszystkich swoich znajomych, a osoba w tłumie zaczyna wierzyć w plotkę, gdy co najmniej połowa jej znajomych w nią wierzy.

Ponieważ od momentu uwierzenia w plotkę nie słucha się już innych opinii, raz przyjęta plotka jest wyznawana nieustannie.

Dowiedzmy się, w jakim czasie ludzie zaczynają wierzyć w plotkę.

Wejście

W pierwszej linii podana jest liczba osób $N$ ($1 \le N \le 200\,000$), co oznacza, że istnieją osoby od numeru 1 do $N$.

Od drugiej linii podane jest $N$ wierszy. W $i$-tym wierszu ($1 \le i \le N$) podane są numery znajomych osoby $i$ oraz liczba $0$ oznaczająca koniec danych w wierszu, oddzielone spacjami. Numery są liczbami naturalnymi od $1$ do $N$, a w jednym wierszu nie ma powtórzonych numerów. Nikt nie jest swoim własnym znajomym ani nie jest znajomym jednostronnie; łączna liczba relacji dwukierunkowych nie przekracza $1\,000\,000$.

W kolejnej linii podana jest liczba pierwotnych nadawców plotki $M$ ($1 \le M \le N$).

W ostatniej linii podane są numery pierwotnych nadawców oddzielone spacjami. Numery pierwotnych nadawców nie powtarzają się.

Wyjście

Wypisz $N$ liczb całkowitych $t_1, t_2, \dots, t_N$ oddzielonych spacjami. $t_i$ to czas (w minutach), w którym osoba $i$ zaczęła wierzyć w plotkę, lub $-1$, jeśli osoba ta nie uwierzy w plotkę nawet po upływie wystarczająco długiego czasu. Przyjmuje się, że pierwotni nadawcy zaczynają wierzyć w plotkę w czasie $0$.

Przykład

Wejście 1

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

Wyjście 1

0 1 2 3 4 0 -1

Wejście 2

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

Wyjście 2

4 4 3 3 2 0 1

Uwagi

• $0$ min: Pierwotni nadawcy (osoby 1 i 6) tworzą plotkę.
• $1$ min: Osoba 1 rozprzestrzenia plotkę na osoby 2 i 3. Osoba 2 wierzy w plotkę, ponieważ 1 z 2 jej znajomych w nią wierzy. Osoba 3 nie wierzy w plotkę, ponieważ tylko 1 z 3 jej znajomych w nią wierzy. Osoba 6 nie ma znajomych, którym mogłaby przekazać plotkę.
• $2$ min: Osoby 1 i 2 rozprzestrzeniają plotkę na osobę 3. Ponieważ co najmniej połowa z 3 sąsiadów (czyli 2 osoby) wierzy w plotkę, osoba 3 również zaczyna w nią wierzyć od 2. minuty.
• $3$ min: Osoba 3 rozprzestrzenia plotkę na osobę 4. Osoba 4 zaczyna wierzyć.
• $4$ min: Osoba 5 również zaczyna wierzyć w plotkę. Osoba 7 nie wierzy w plotkę nawet po upływie wystarczająco długiego czasu.