zhx has built a tree of $n$ nodes. On each node of the tree live a boy and a girl. The weight and height of them are already known.
One day, zhx was bored of brushing problems, so he asked you to find a boy and a girl on the path between u and v (not necessary to live on the same node). He wants you to maximize the weighted average height of them.
Note: Let's assume that the boy's weight is $wb$ and his height is $hb$, and the girl's weight is $wg$ and her height is $hg$, then the answer should be $\frac{wb * hb + wg * hg}{wb + wg}$.
Input
Multiply test cases(less than $10$. Cases in which $n > {10}^{4}$ will not exceed $3$). Seek $EOF$ as the end of the file.
For each case, there are two integers $n, q$ in the first line.($n,q \leq 3*10^{4}$)
In the following $n$ lines, there are four integers $wb_i, hb_i, wg_i, hg_i$($1 \leq wb_i, hb_i, wg_i, hg_i \leq 10^{3}$), indicating the weight and the height of the boy and the girl on node $i$.
Then comes $n - 1$ lines with two integers, indicating edges of the tree.(nodes are numbered from $1$ to $n$)
Then comes $q$ lines with two integers $u, v$ indicating an query.
Output
For each query, output a simplified fraction as the answer.(That means if your answer is $\frac{a}{b}$, $a$ and $b$ should not have a common divisor larger than $1$)
