Given a tree $G$ with $n$ nodes and an integer $E$.

You need to assign an integer weight $w_i$ to each edge in the tree $G$ such that:

• $1 \le w_i \le 10^9$;
• The expected value of $\max\limits_{v=1}^n\operatorname{dis}(u,v)$ when a node $u$ is chosen uniformly at random, modulo $998244353$, is equal to $E$;

Or report that no such assignment exists.

Here, $\operatorname{dis}(u,v)$ denotes the sum of edge weights on the simple path between nodes $u$ and $v$.

Input

The first line contains an integer $n$.

The next $n-1$ lines each contain two positive integers $u_i, v_i$, representing an edge $(u_i, v_i)$ in the tree $G$.

The next line contains an integer $E$.

Output

Output either one line or $n-1$ lines:

• If a solution exists, output $n-1$ lines, each containing an integer $w_i$, representing the weight of the edge $(u_i, v_i)$ in your constructed tree $G$.
• If no solution exists, output a single line containing the integer $-1$.

Any valid output is acceptable.

Examples

Input 1

3
1 2
2 3
665496238

Output 1

1
2

Note 1

All $\operatorname{dis}$ values are shown in the table below, where the maximum $\operatorname{dis}$ for each starting node is highlighted in red.

It can be verified that $E=\dfrac{3+2+3}{3}=\dfrac{8}{3}\equiv 665496238\pmod {998244353}$.

Constraints

For all test cases, $2\le n\le 10^5$, $1 \le u_i,v_i \le n$, $0\le E < 998244353$, and the input is guaranteed to form a tree.