Score : 600 points
There is a tree with N vertices numbered 1 to N. The i-th edge in this tree connects Vertex a_i and Vertex b_i, and the color and length of that edge are c_i and d_i, respectively. Here the color of each edge is represented by an integer between 1 and N-1 (inclusive). The same integer corresponds to the same color, and different integers correspond to different colors.
Answer the following Q queries:
Input is given from Standard Input in the following format:
N Q a_1 b_1 c_1 d_1 : a_{N-1} b_{N-1} c_{N-1} d_{N-1} x_1 y_1 u_1 v_1 : x_Q y_Q u_Q v_Q
Print Q lines. The j-th line (1 \leq j \leq Q) should contain the answer to Query j.
5 3 1 2 1 10 1 3 2 20 2 4 4 30 5 2 1 40 1 100 1 4 1 100 1 5 3 1000 3 4
130 200 60
The graph in this input is as follows:
Here the edges of Color 1 are shown as solid red lines, the edge of Color 2 is shown as a bold green line, and the edge of Color 4 is shown as a blue dashed line.