徒步羊（hike）

问题背景

咩咩山是一个著名的户外徒步旅游区。

问题描述

整个区域共有 $n$ 个地标，编号 $1\ldots n$，有 $n-1$ 条双向道路，每条道路连接两个地标。保证任意两个地标可以通过若干条道路连通。每条道路有一个正整数 $w$ 表示危险度。

现要开发 $n$ 条徒步路线，其中第 $i$ 条路线要由 $i$ 条互不重复且首尾相接的道路组成，即一条包含 $i$ 条道路的简单路径。不同条路线之间没有任何相互约束。

根据当地奇怪的风俗，一条路线的价值等于其上所有道路危险度的最大公约数。求对所有 $i=1\ldots n$，路线 $i$ 最大的可能价值是多少。

输入格式

从文件 hike.in 中读取数据。

第一行一个正整数 $n$。

下面 $n-1$ 行每行三个正整数 $u,v,w$，表示地标 $u,v$ 间存在一条危险度为 $w$ 的道路。

数据保证任何两个地标之间可以通过道路连通。

输出格式

输出到文件 hike.out。

输出 $n$ 行，每行一个整数，依次表示 $i=1\ldots n$ 的答案。如不存在包含 $i$ 条道路的路线，则对应行输出 0。

样例 1

3
1 2 3
1 3 9

9
3
0

样例 1 解释

• $i=1$ 时，选 $1\rightarrow 3$，价值为 $9$。
• $i=2$ 时，选 $2\rightarrow 1\rightarrow 3$，价值为 $\gcd(3,9)=3$。
• $i=3$ 时，不存在包含三条道路的路线。

数据规模与约定

• 20% 的数据，$n\leq 3$。
• 40% 的数据，$n\leq 100$。
• 70% 的数据，$n\leq 3000$。
• 100% 的数据，$1\leq n\leq 100000$，$1\leq u,v\leq n$，$1\leq w\leq 1000000$。
• 所有的数据中，共有 30% 的数据，$w$ 全都相同。

所有测试点时限均为 1 秒，内存限制均为 512 MiB。

文件读写说明

必须使用文件读写。在 main 函数开头加入：

freopen("hike.in", "r", stdin);
freopen("hike.out", "w", stdout);