Given an unrooted tree with $n$ nodes and weighted edges, each node is assigned a unique label from a permutation of $1 \sim n$.

There are $m$ queries. Each query provides $l$ and $r$, and you are asked to calculate the sum of distances on the tree for all pairs of nodes $(i, j)$ such that $l \le i < j \le r$. The distance between two nodes is defined as the sum of the weights of the edges on the simple path connecting them.

Input

The first line contains two space-separated integers $n$ and $m$.

The next $n-1$ lines each contain three space-separated integers $u$, $v$, and $d$, representing an edge between $u$ and $v$ with weight $d$.

The next $m$ lines each contain two space-separated integers $l$ and $r$, representing a query.

Output

Output $m$ lines, each containing the answer for the corresponding query, modulo $2^{32}$.

Examples

Input 1

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

Output 1

19
26
18
28
44
0

Subtasks

Idea: nzhtl1477, Solution: nzhtl1477, Code: zx2003, Data: nzhtl1477

For $100\%$ of the data, $1 \le n, m, d \le 2 \cdot 10^5$, and all values are integers.