CF526G.Spiders Evil Plan

Spiders are Om Nom's old enemies. They love eating candies as much as he does and that's why they keep trying to keep the monster away from his favorite candies. They came up with an evil plan to trap Om Nom.

Let's consider a rope structure consisting of n nodes and n - 1 ropes connecting the nodes. The structure is connected, thus, the ropes and the nodes form a tree. Each rope of the formed structure is associated with its length. A candy is tied to node x of the structure. Om Nom really wants to eat this candy.

The y spiders are trying to stop him from doing it. They decided to entangle the candy and some part of the structure into a web, thus attaching the candy to as large as possible part of the rope structure.

Each spider can use his web to cover all ropes on the path between two arbitrary nodes a and b. Thus, y spiders can cover the set of ropes which is a union of y paths in the given tree. These y paths can arbitrarily intersect each other. The spiders want the following conditions to be hold:

• the node containing the candy is adjacent to at least one rope covered with a web
• the ropes covered with the web form a connected structure (what's the idea of covering with a web the ropes that are not connected with the candy?)
• the total length of the ropes covered with web is as large as possible

The spiders haven't yet decided to what node of the structure they will tie the candy and how many spiders will cover the structure with web, so they asked you to help them. Help them calculate the optimal plan for multiple values of x and y.

蜘蛛是奥姆·诺姆的老对手。它们和奥姆·诺姆一样酷爱糖果，因此总是试图将这个小怪物挡在它最喜爱的糖果之外。它们想出了一个邪恶的计划来设下陷阱困住奥姆·诺姆。

我们考虑一种由 $n$ 个节点和 $n-1$ 条绳子构成的绳索结构，这些绳子连接着各个节点。该结构是连通的，因此这些绳子与节点构成一棵树。每条绳子都具有其对应的长度。一颗糖果被系在该结构的节点 $x$ 上。奥姆·诺姆非常想吃到这颗糖果。

$y$ 只蜘蛛正试图阻止他这么做。它们决定用蛛网缠住糖果以及结构的某一部分，从而将糖果尽可能大范围地固定在绳索结构上。

每只蜘蛛可用其蛛网覆盖任意两个节点 $a$ 和 $b$ 之间路径上的所有绳子。因此，$y$ 只蜘蛛所能覆盖的绳子集合，即为该树中 $y$ 条路径的并集。这 $y$ 条路径可以任意相交。蜘蛛们希望满足以下条件：

• 包含糖果的节点至少与一条被蛛网覆盖的绳子相邻；
• 被蛛网覆盖的绳子构成一个连通结构（否则，若被覆盖的绳子不与糖果所在位置连通，那用蛛网覆盖它们又有何意义？）；
• 被蛛网覆盖的绳子的总长度尽可能大。

蜘蛛们尚未决定将糖果系在结构的哪一个节点上，也未确定将派出多少只蜘蛛来用蛛网覆盖该结构，因此它们请你帮忙。请帮助它们针对多组不同的 $x$ 和 $y$ 值，计算出最优方案。

The first line contains numbers n and q (1 ≤ n, q ≤ 105) — the number of nodes in the structure and the number of questions that the spiders want to ask you.

The next n - 1 lines determine the rope structure. The i-th line contains three integers u__i, v__i, l__i (1 ≤ u__i, v__i ≤ n, u__i ≠ v__i, 1 ≤ l__i ≤ 1000), showing that there is a rope of length l__i between nodes u__i and v__i.

Next q lines describe the spiders' questions. As they want you to answer their question online, they encoded their messages in a special manner.

Each of the next q lines contains two numbers x__i, y__i. In the first question of the spiders x = _x_1, y = _y_1.

To calculate values x and y in the spiders' i-th (2 ≤ i ≤ q) question, you need to use the following formulas:

where Ans__i - 1 is the total length of the ropes covered by a web in the answer for the (i - 1)-th question.

The following inequality holds: 1 ≤ x__i, y__i ≤ n.

第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 10^5$）——分别表示该结构中的节点数以及蜘蛛们想要向你提出的询问次数。

接下来的 $n-1$ 行描述绳索结构。第 $i$ 行包含三个整数 $u_i,\ v_i,\ l_i$（$1 \leq u_i,\ v_i \leq n$，$u_i \ne v_i$，$1 \leq l_i \leq 1000$），表示节点 $u_i$ 与 $v_i$ 之间有一条长度为 $l_i$ 的绳索。

接下来的 $q$ 行描述蜘蛛们的询问。由于它们要求你在线回答其问题，因此对消息进行了特殊编码。

接下来的每行包含两个数 $x_i,\ y_i$。在蜘蛛们的第一个问题中，$x = x_1,\ y = y_1$。

为计算蜘蛛们第 $i$ 个问题（$2 \leq i \leq q$）中的 $x$ 和 $y$ 值，需使用如下公式：

其中 $Ans_{i-1}$ 表示第 $(i-1)$ 个问题的答案中被蛛网覆盖的所有绳索的总长度。

以下不等式恒成立：$1 \leq x_i,\ y_i \leq n$。

For each question of the spiders print on a separate line a single integer Ans__i — the total length of the ropes covered with web in the optimal plan.

对于每只蜘蛛的问题，请在单独一行输出一个整数 $Ans_i$ —— 最优方案中被蛛网覆盖的绳子总长度。