#898 Star Tree

Statement

Statement language

You are given a tree whose vertices are numbered from $1$ to $N$ . Initially, every vertex has value $0$ .

Process $Q$ queries of the following form.

$x\ y$ : Let $a_1,a_2,\ldots,a_k$ be the vertices on the unique simple path from vertex to vertex , in that order. For each , add to the value of vertex . Here , , and .

Both endpoints are included. Reversing a query can change the amounts added. After processing all queries, find the value of each vertex modulo $998\,244\,353$ .

Input

The input is given in the following format. The first line contains the number of vertices $N$ and the number of queries $Q$ . Each of the next $N-1$ lines describes an edge $u_i,v_i$ , and each of the following lines gives a query . There are no edge lines when and no query lines when .

Output

Print the final values of vertices $1,2,\ldots,N$ , each reduced modulo $998\,244\,353$ , on one line separated by spaces.

Constraints

$1\leq N\leq500\,000$ .
$0\leq Q\leq500\,000$ .
$1 \leq u_{}$ , ().

Subtasks

#	Score	Constraints
1	20	$N\leq2000$ ; $Q\leq2000$ .
2	25	For every $1\leq i<N$ , there is an edge between vertices and .

Samples

Sample 1

Input

Output

3 3 5 5 3

The query paths are $2,1,3,4$ , then $4,3,5$ , then $1,2$ . The final values in vertex order are .