TeaTree

Recently, TeaTree acquire new knowledge gcd(Greatest Commen Divisor), now she want to test you.
As we know, teaTree is a tree and her root is node 1, she have n nodes and n-1 edges, for each node i, it has it’s value v[i].
For every two node i and j(i is not equal to j), they will tell their Lowest Commen Ancestors(LCA) a number:gcd(v[i],v[j]).
For each node, you have to calculate the max number that it heard. some definition:
In graph theory and computer science, the lowest commen ancestor(LCA) of two nodes u and v in a tree is the lowest(deepest) node that both u and v as descendants, where we define each node to be a descendant of itself.

Input:
On the first line, there is a positive integer n, which describe the number of nodes.
Next line there are n-1 positive integers f[2], f[3], …, f[n], f[i] describe the father of node i on tree.
Next line there are n positive integers v[2], v[3], … , v[n], v[i] describe the value of node i.
n <=100000, f[i]<i, v[i]<=100000

Output:
Your output should include n lines, for i-th line, output the max number that node i heard.
For the nodes who heard nothing, output -1.

Sample Input

4
1 1 3
4 1 6 9

Sample Output

2
-1
3
-1

-------------本文结束感谢您的阅读-------------