题目描述

求一棵 $N-2$ 条边权确定的树中那条不确定的边的边权分别为 $[L,R]$ 中的每一个数时树中路径权值 $\text{gcd}$ 为 $1$ 的点对有多少。

路径的 $\text{gcd}$ 为所有边权的 $\text{gcd}$

输入格式

第一行 $N,L,R$。

第二行是不确定的边的两个端点。

接下来 $N-2$ 行每行三个数表示一条边的两个端点和边权。

输出格式

$L-R+1$ 行，第 $i$ 行为当不确定边权等于 $L+i-1$ 时的答案。

样例

input

5 1 5
1 2
2 3 6
2 4 4
1 5 3

output

6
3
2
3
5

数据范围与提示

对于 $30\%$ 的数据, 满足 $N ≤ 1000, R − L ≤ 1000$;

对于另外的 $30\%$ 的数据, 满足 $N ≤ 10^5, L = R$;

对于 $100\%$ 的数据, 满足 $N ≤ 10^5, Di ≤ 10^5, 1 ≤ L ≤ R ≤ 10^5$ .

传题人: 「注意：版权归杨乐所属！！」