题目描述

一张通信网是一棵有 $n$ 个节点的无向树，节点编号 $1$ 到 $n$。树的每条边都安装着一盏灯，颜色为 0 或 1；改变该边灯的颜色一次需要支付 $w$ 单位费用。

现有 $q$ 次互相独立的巡线检查，每次给出两个节点 $u,v$。

沿着树上从 $u$ 到 $v$ 的简单路径依次观察经过的边灯。为完成本次检查，需要使路径上相邻两条边的颜色不同。允许任意选择第一条边的颜色；不在该路径上的边无需改变。

请分别计算每次检查所需的最少改灯费用。每次检查结束后，所有灯恢复为最初的颜色；一次检查中的修改不会影响其它检查。

如果路径没有边（$u=v$）或只有一条边，答案为 $0$。

输入格式

第一行两个整数 $n,q$。

接下来 $n-1$ 行，每行四个整数 $u,v,c,w$，表示一条树边、初始颜色和改色费用。

接下来 $q$ 行，每行两个整数 $u,v$，表示一次巡线检查。

输出格式

输出 $q$ 行，每行一个整数，表示最少改灯费用。

样例 1

4 4
1 2 0 4
2 3 0 7
2 4 1 3
1 3
1 4
3 4
1 1

4
0
0
0

样例解释

路径 $1\to2\to3$ 上的两盏灯均为 0，只需修改其中较便宜的第一盏灯，费用 $4$。路径 $1\to2\to4$ 和 $3\to2\to4$ 已经交替，无需修改。

数据范围与部分分

保证 $2\le n\le2\times10^5$，$1\le q\le2\times10^5$，$c\in\{0,1\}$，$1\le w\le10^9$；输入保证前 $n-1$ 条边构成一棵树。

树上的路径必须使用原图的初始颜色计算；若错误地将各查询累积修改，答案会不正确。