You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

最近，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