Given a tree with $n$ nodes rooted at $1$, each node has an index and each edge has a weight.

Define $dep(x)$ as the sum of edge weights on the simple path from the root to node $x$, and $lca(x,y)$ as the lowest common ancestor of nodes $x$ and $y$ in the tree.

There are $m$ queries. Each query provides $l$ and $r$. For all pairs of node indices $(i, j)$ such that $l \le i, j \le r$, find the number of distinct values of $dep(lca(i, j))$.

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, 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 an integer representing the answer to the query.

Examples

Input 1

10 19
9 1 -4
9 8 2
8 10 5
9 7 -3
1 4 2
10 2 5
10 5 -1
7 3 -3
10 6 5
8 10
4 6
1 7
7 9
5 5
7 8
8 10
10 10
10 10
9 10
5 7
8 8
6 6
2 8
9 10
4 8
5 5
1 6
1 2

Output 1

3
4
7
3
1
3
3
1
1
2
5
1
1
8
2
7
1
6
2

Input 2

10 19
6 1 299830931
1 4 -565297395
1 7 -606073228
4 8 94253706
8 9 -576603423
4 3 116780102
3 5 620388954
7 10 -950023905
5 2 813045783
3 5
7 7
8 10
4 7
10 10
9 9
4 7
8 10
6 7
4 8
9 10
2 9
8 10
2 8
4 4
10 10
4 9
1 5
8 9

Output 2

3
1
4
5
1
1
5
4
3
6
3
9
4
8
1
1
7
5
2

Subtasks

Idea: nzhtl1477, Solution: nzhtl1477, Code: lk, Data: nzhtl1477

For $10\%$ of the data, $1 \le n, m \le 100$.

For another $20\%$ of the data, $1 \le n, m \le 5000$.

For another $20\%$ of the data, $1 \le n, m \le 50000$.

For another $20\%$ of the data, $d = 1$.

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