Description

有一个 N 个节点的树，每条边有颜色、边权。

处理 Q 个询问，每个询问给出 x_i,y_i,u_i,v_i ，您需要求出假定所有颜色为 x_i 的边边权

全部变成 y_i 后，u_i 和 v_i 之间的距离。

询问之间互相独立。

Format

Input

第一行二个数N,Q

接下来N-1行，给出树的形态,边权长度<=1e4

再接下Q行，每行给出x_i,y_i,u_i,v_i

N<=1e5

2<=Q<=1e5

Output

如题

Samples

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