Kazari loves to solve math problems.
In her opinion, all problems can be divided into three categories according to their difficulties - Easy, Medium and Hard, represented as $1, 2$ and $3$, respectively.
Today she goes to the forest and finds a strange tree with $n$ vertices: there is a problem on each edge!
Formally, the $i$-th edge on the tree directly connects vertex $u_i$ and $v_i$ and contains a math problem which belongs to $c_i$ category.
She makes a decision that she will choose two endpoints $s, t$ and walk from $t$ to $s$ on each of next $m$ days. During her walk, she must solve all problems that she will go through, but unfortunately, not on all days she will be able to do that - because the problems may be too hard!
More precisely, Kazari is able to solve all categories of problems at the beginning of a day, however, once she solve a Hard problem, she will lose all her faith at once, in the rest of the day she is only able to solve Easy problems, i.e., if she is encountered with a Medium or Hard problem during this time, she will fail.
There is a piece of good news that on each morning of next $m$ days, exactly one problem will be chosen to become easier, i.e., a Hard problem will become a Medium problem, a Medium problem will become a Easy problem, a Easy problem will remain the same. Note that the effect is persistent.
Kazari would like to know, for each day, whether she is able to reach $s$ from $t$ and how many vertices from which she is able to reach $s$ among all $n$ vertices.

The first line of the input contains an integer $T$ denoting the number of test cases.
Each test case starts with two integers $n, m$ $(1 \le n, m \le 10 ^ 5, \sum{n}, \sum{m} \le 3 \times 10 ^ 5)$ denoting the number of vertices and the number of days. Each of next $n - 1$ lines contains three integers $u_i, v_i, c_i$ $(1 \le u_i \neq v_i \le n, 1 \le c_i \le 3)$ describing an edge. Each of next $m$ lines contains four integers $a_i, b_i, s_i, t_i$ $(1 \le a_i \neq b_i \le n, 1 \le s_i, t_i \le n)$, $(a_i, b_i)$ represents the edge where the problem is chosen to become easier and $s_i, t_i$ represents the two endpoints that the girl chooses this day.

For each test case, print two integers for each day, the first integer denotes whether the girl is able to reach $s$ and the second integer denotes the number of vertices from which she is able to reach $s$.