Recently, TeaTree acquire new knoledge gcd (Greatest Common 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 edge, for each node i, it has it’s value v[i]. For every two nodes i and j (i is not equal to j), they will tell their Lowest Common 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 common ancestor (LCA) of two nodes u and v in a tree is the lowest (deepest) node that has both u and v as descendants, where we define each node to be a descendant of itself.
输入解释
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
输出解释
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.