Type: Default 6000ms 1024MiB

[2026 CCPC_NC_I B] 世界树

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

给定一棵 nn 个节点的无根树 TT,节点编号为 11 到 nn,每条边有一个整数边权(可能为负)。

定义树上两点 a,ba,b 的距离 dis⁡(a,b)\operatorname{dis}(a,b) 为它们之间的唯一简单路径上的边权之和。

现有 qq 次查询,每次查询给定两个节点 xx 和 yy,请你计算并输出:

$$\max_{u \in T}(\operatorname{dis}(x,u)+\operatorname{dis}(y,u))$$

Format

Input

第一行两个整数 n,qn,q (1≤n,q≤5×1051 \le n,q \le 5 \times 10^5),分别表示树的节点数和查询次数。

接下来 n−1n-1 行,每行三个整数 u,v,wu,v,w (1≤u,v≤n1 \le u,v \le n, ∣w∣≤109|w| \le 10^9),表示节点 uu 与节点 vv 之间有一条边权为 ww 的边。保证输入构成一棵树。

接下来 qq 行,每行两个整数 x,yx,y (1≤x,y≤n1 \le x,y \le n),表示一次查询。

Output

共 qq 行,对于每次查询,输出一行一个整数,表示所求的最大值。

Samples

4 3
1 2 1
2 3 2
2 4 -1
1 1
1 2
1 3
6
5
3