Dano je \(n\) brojeva \(x_i\) i svaki broj ima svoju boju \(c_i\). Za svaki broj pronađite koliko je njemu udaljen najbliži broj različite boje. Udaljenost \(i\)-tog broja i \(j\)-tog broja je \(\left|x_i - x_j\right|\).

Ulaz

U prvom retku nalazi se broj \(n\) \((2 \leq n \leq 10^5)\).

U sljedećem retku nalazi se \(n\) brojeva (ne nužno sortiranih) \(x_i\), \((-10^8 \leq x_i \leq 10^8)\).

U posljednjem retku nalazi se \(n\) brojeva \(c_i\), \((1 \leq c_i \leq n)\), boje brojeva.

U svim testnim primjerima nalazit će se barem dvije različite boje.

Izlaz

U jedini redak ispišite \(n\) brojeva, redom kako su dani brojevi \(x_i\), udaljetnost tog broja do najbližeg broja različite boje.

U 50% testnih primjera će vrijediti \(2 \leq n \leq 1000\).

Primjer ulaza

3
100 1 -100
1 2 3

Primjer izlaza

99 99 101

Primjer ulaza

3
3 1 4
1 2 1

Primjer izlaza

2 2 3

Primjer ulaza

5
10 23 22 13 1000
1 2 1 1 2

Primjer izlaza

13 1 1 10 978