C. Costly Roads
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ vertices connected by $$$n-1$$$ roads. Ignoring direction, the roads form a tree.

For every road, traveling in its two directions may have different costs. An input line $$$u\ v\ a\ b$$$ means that traveling from $$$u$$$ to $$$v$$$ costs $$$a$$$, while traveling from $$$v$$$ to $$$u$$$ costs $$$b$$$.

For every possible starting vertex $$$r$$$, find the sum of the costs of the unique directed trips from $$$r$$$ to all vertices. The trip from $$$r$$$ to itself has cost zero.

Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$).

Each of the next $$$n-1$$$ lines contains four integers $$$u$$$, $$$v$$$, $$$a$$$, and $$$b$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$, $$$1 \le a,b \le 10^6$$$). The undirected edges $$$(u,v)$$$ form a tree. The costs of directions $$$u\to v$$$ and $$$v\to u$$$ are $$$a$$$ and $$$b$$$, respectively.

Output

Print $$$n$$$ integers. The $$$r$$$-th integer must be the sum of travel costs from vertex $$$r$$$ to every vertex.

Examples
Input
1
Output
0
Input
3
1 2 4 7
2 3 2 5
Output
10 9 17
Input
4
2 1 3 8
2 3 4 6
4 2 5 2
Output
30 9 23 22
Note

All required sums fit in signed 64-bit integers.