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.

时间限制：$4s$，空间限制：$512MB$

题目描述：

​ 有一棵$n$个点的无根树。

​ 小F每次会给小Y一个区间$[l,r]$，让小Y求出节点编号在$[l,r]$中的两点距离最大值，即$\max_{l\le x,y\le r}{dis(x,y)}$。

​ 小F一共会给出$m$组询问，由于询问过多，小Y希望你可以帮帮她。

输入格式

​ 输入文件名为$tree.in$

​ 输入文件的第一行包含$1$个正整数$n$，表示树的节点个数。

​ 接下来$n-1$行每行$3$个正整数$x,y,z$，表示$x$和$y$之间有一条长度为$z$的边。

​ 接下来一行包含$1$个正整数$m$，表示一共有$m$组询问。

​ 接下来$m$行每行包含$2$个正整数$l,r$，表示询问区间为$[l,r]$。

输出格式

​ 输出文件名为$tree.out$。

​ 输出$m$行每行包含一个正整数，表示两点距离的最大值。

样例

样例1

输入数据：

5
1 2 1
1 3 5
2 4 2
2 5 2
3
1 5
4 5
1 3

输出数据：

8
4
6

样例2

见选手目录下的tree2.in和tree2.ans。

数据范围与约定

​ 对于$20\%$的数据，满足$1\le n,m\le 10^2$。

​ 对于$40\%$的数据，满足$1\le n,m\le 10^3$。

​ 对于另$10\%$的数据，满足$l=1,\ r=n$。

​ 对于另$20\%$的数据，满足$l=1$。

​ 对于$100\%$的数据，满足$1\le n,m\le 10^5,\ 1\le z\le 10^5,\ 1\le l\le r\le n$。