Do you believe in rumors?

In a famous psychology experiment, people were shown two lines and asked which one was longer. In reality, everyone except one person was a confederate of the experimenter. The confederates claimed that the shorter line was actually longer. When everyone around them gave the same answer, the real subject also claimed that the shorter line was longer. This experiment showed that people are strongly influenced by those around them, and rumors are the same.

A rumor starts from the initial spreaders. There can be multiple initial spreaders, and no one creates and believes a rumor on their own except for the initial spreaders.

Every minute, people who believe the rumor spread it to all their acquaintances simultaneously, and a person in the crowd starts believing the rumor if at least half of their acquaintances believe it.

Since people do not listen to other things once they start believing a rumor, they continue to believe it once they start.

In this problem, let's find out the time when people first start believing the rumor.

Input

The first line contains the number of people $N$. ($1 \le N \le 200\,000$) This means there are people from $1$ to $N$.

From the second line, $N$ lines are given. The $i$-th line ($1 \le i \le N$) contains the IDs of the acquaintances of person $i$, followed by a $0$ indicating the end of the input for that line, separated by spaces. The IDs are natural numbers between $1$ and $N$, and there are no duplicate IDs on the same line. No one is their own acquaintance, and there are no one-way acquaintance relationships; the total number of bidirectional acquaintance relationships does not exceed $1\,000\,000$.

The next line contains the number of initial spreaders $M$. ($1 \le M \le N$)

The last line contains the IDs of the initial spreaders, separated by spaces. The IDs of the initial spreaders are distinct.

Output

Output $N$ integers $t_1, t_2, \dots, t_N$ separated by spaces. $t_i$ is the time (in minutes) when person $i$ first starts believing the rumor, or $-1$ if they do not believe the rumor even after a sufficiently long time. Assume that the initial spreaders start believing the rumor at $0$ minutes.

Examples

Input 1

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

Output 1

0 1 2 3 4 0 -1

Input 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

Output 2

4 4 3 3 2 0 1

Note

Example 1:

0 minutes: The initial spreaders (person 1 and person 6) create the rumor.

1 minute: Person 1 spreads the rumor to persons 2 and 3. Person 2 starts believing the rumor because 1 out of their 2 acquaintances believes it. Person 3 does not believe the rumor because only 1 out of their 3 acquaintances believes it. Person 6 has no acquaintances to spread the rumor to.

2 minutes: Persons 1 and 2 spread the rumor to person 3. Since 2 out of their 3 neighbors (which is at least half) believe the rumor, person 3 also starts believing it at 2 minutes.

3 minutes: Person 3 spreads the rumor to person 4. Person 4 starts believing it.

4 minutes: Person 5 also starts believing the rumor. Person 7 does not believe the rumor even after a sufficiently long time.

Figure 1. Visualization of the rumor spreading process for Example 1.