Coloring Geysers

Once, Lucy found a cave on one of the planets in the Link-Cut system. The cave consists of $n$ halls and $n-1$ passages; each passage connects two halls, and it is possible to reach any other hall from any hall through the passages.

In each hall, there is a coloring geyser. When the coloring geyser in hall number $i$ erupts, it colors all halls that are at a distance of no more than $d_i$ from hall $i$ in color number $i$. The distance between two halls is defined as the minimum number of passages you need to travel through in order to move between them.

Lucy knows the structure of the cave, the colors of some halls, and that each geyser erupted exactly once. Based on this information, determine any possible order in which the eruptions could have occurred.

Input

The first line contains a single integer $n$ $(2\le n\le 10^5)$ — the number of halls in the cave.

The second line contains $n$ integers $d_1,d_2,...,d_n$ $(0\le d_i\le n-1)$ — the distance coloring parameters for the geysers.

The third line contains $n$ integers $c_1,c_2,...,c_n$ $(-1\le c_i\le n)$, where $c_i$ is either the color number of the $i$-th hall or $-1$, if the color of the $i$-th hall is unknown.

The next $n-1$ lines describe the passages. The $i$-th line contains two integers $u_i,v_i$ $(1\le u_i,v_i\le n,u_i\ne v_i)$ — the halls connected by the passage.

Output

In a single line, output $n$ integers $p_1,p_2,...,p_n$, where $p_i$ is the number of the hall where the geyser which erupted $i$-th is located. It is guaranteed that there is at least one order that corresponds to the input data.

Examples

Note

In the first example, here are the colors of halls after each eruption, assuming they happened in the order given in output:

• $1,1,1,1,1$

• $5,1,1,1,5$

• $4,1,1,4,5$

• $3,1,3,4,5$

• $2,2,3,4,5$

Scoring

1. ($10$ points): $n\le 8$;

2. ($40$ points): $d_i=1(1\le i\le n)$;

3. ($30$ points): $u_i=1(1\le i\le n-1)$;

4. ($80$ points): $n\le 5\cdot 10^4$;

5. ($65$ points): no additional constraints.