I. Closer or Equal
time limit per test
4 с
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ vertices. The score of every vertex is initially $$$0$$$.

You have to process $$$q$$$ queries. Each query contains five integers $$$u$$$, $$$v$$$, $$$x$$$, $$$y$$$, and $$$z$$$. For every vertex $$$r$$$:

  • add $$$x$$$ to its score if $$$\operatorname{dist}(r,u) \lt \operatorname{dist}(r,v)$$$;
  • add $$$y$$$ to its score if $$$\operatorname{dist}(r,u) \gt \operatorname{dist}(r,v)$$$;
  • add $$$z$$$ to its score if $$$\operatorname{dist}(r,u) = \operatorname{dist}(r,v)$$$.

Here, $$$\operatorname{dist}(a,b)$$$ is the number of edges on the simple path between vertices $$$a$$$ and $$$b$$$.

After every query, print the minimum score among all vertices and the number of vertices having this score.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 2\cdot 10^5$$$) — the number of vertices and the number of queries.

Each of the next $$$n-1$$$ lines contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a,b \le n$$$, $$$a \ne b$$$), denoting an edge between vertices $$$a$$$ and $$$b$$$. The given edges form a tree.

Each of the next $$$q$$$ lines contains five integers $$$u$$$, $$$v$$$, $$$x$$$, $$$y$$$, and $$$z$$$ ($$$1 \le u,v \le n$$$, $$$0 \le x,y,z \le 10^9$$$), describing a query.

Output

After every query, print two integers: the minimum score among all vertices and the number of vertices having this score.

Example
Input
4 4
1 2
1 3
1 4
2 3 4 4 1
2 4 0 5 2
1 2 3 0 7
3 3 10 20 2
Output
1 2
3 1
4 1
6 1
Note

After the first query, the scores of vertices $$$1,2,3,4$$$ are $$$1,4,4,1$$$, respectively. Thus, the minimum score is $$$1$$$, and two vertices have it.

In the last query, $$$u=v=3$$$, so every vertex is equally far from $$$u$$$ and $$$v$$$. Therefore, $$$z=2$$$ is added to every score.