Background

土拨鼠桐桐拥有庞大的家族, 这一天, 土拨鼠桐桐想要知道如果他想拉帮结派组成一个"犯罪团伙", 需要花费多少金币收买土拨鼠亲戚.

Description

给你一棵土拨鼠桐桐家族的族谱, 这是一棵树, 老祖父的为根节点1, 每一个节点都表示一只土拨鼠, 起初, 土拨鼠桐桐可以任选一个位置作为起点, 消耗$1$点"金币". 然后你可以拉拢你已入伙的土拨鼠的父亲节点花费$a$的"金币", 也可以花费$b$的金币去拉拢已经入伙的土拨鼠的子节点.

你现在想知道, 你拉拢$k$只土拨鼠的最小花费金币$c$是多少?

Format

Input

输入共$n$行.

第一行输入三个整数$n, a, b$.

接下来$n-1$行每行输入两个正整数$w, v$, 表示族谱树中的一条边(不确定谁是父亲节点, 谁是子节点).

Output

输出共$n$行, 每行输出一个整数.

第$i$行表示$k=i$时最小的$c$.

Samples

样例1

5 1 2
1 2
2 3
3 4
4 5

1
2
3
4
5

样例解释1

这棵树是一条链。

对于 $k=1\sim n，$选取最下方的 $5$ 号节点，往上走 $k-1$ 个节点，每次向上是消耗为 $a=1$ 的金币。

所以对于 $k=i$，输出 $i$。

样例2

5 2 3
1 2
1 3
4 2
2 5

1
3
5
8
11

样例解释2

$k=1$ 时，随便选择一个节点，花费为 $1$。

$k=2$ 时，选择除了一号节点外的任意一个节点，花费为 $1$，然后选择一个父节点，花费为 $2$，总花费为 $3$。

$k=3$ 时，与 $k=2$ 同理。

$k=4$ 时，选择最长的链的同时，需要分出一个枝杈，多花费 $3$。

$k=5$时，分出两个枝杈，多花费 $6$，总答案为 $5+6=11$。

Limitation

对于 $30\%$ 的数据，$1\leq n,a,b\leq 10$。

对于另外 $30\%$ 的数据，$1\leq n\leq 10^3$。

对于所有数据，$1\leq n\leq 10^5，1\leq a<b\leq n^2$。

注意

文件重定向, tree.in, tree.out