题目描述

最近，TeaTree 学习了新的知识——最大公约数（Greatest Common Divisor，简称 gcd），现在她想考考你。

如我们所知，TeaTree 是一棵树，它的根节点是节点 1，这棵树有 $n$ 个节点和 $n - 1$ 条边。对于每个节点 $i$，它都有一个值 $v_i$。

对于每两个节点 $i$ 和 $j$（$i \neq j$），它们会向它们的最近公共祖先（Lowest Common Ancestors，简称 LCA）告知一个数字：$gcd(v_i, v_j)$。

输入格式

第一行是一个正整数 $n$，表示节点的数量。

接下来一行有 $n - 1$ 个正整数 $f_2, f_3, …, f_n$，$f_i$ 表示节点 $i$ 在树中的父节点。

再接下来一行有 n 个正整数 $v_1, v_2, …, v_n$，$v_i$ 表示节点 i 的值。

$n \le 100000，f_i < i，v_i \le 100000$

输出格式

你的输出应该包含 n 行，对于第 i 行，输出节点 i 所听到的最大数字。

对于没有听到任何数字的节点，输出 -1。

4
1 1 3
4 1 6 9

2
-1
3
-1