Xiao C is the president of country F. Although this country only exists in an online game, he is indeed its president.

Country F consists of $n$ cities, and these $n$ cities are connected by $n-1$ bidirectional roads. It is guaranteed that one can travel from any city to any other city using these $n-1$ bidirectional roads.

Of course, using these bidirectional roads incurs a cost. Passing through the $i$-th bidirectional road requires a cost of $c_i$. We call $c_i$ the cost of the $i$-th bidirectional road.

We define $cost(x,y)$ as the sum of the costs of all bidirectional roads on the simple path from city $x$ to city $y$. Specifically, when $x=y$, $cost(x,y)=0$.

To promote the development of country F, Xiao C has built a new city, $n+1$. Now he needs to build one more bidirectional road so that city $n+1$ can also reach any other city through the $n$ bidirectional roads.

He has $q$ proposals for the new road, each given by two parameters $k_i$ and $w_i$. For each proposal, you need to calculate the sum of all $cost(i,j)$ after adding a bidirectional road connecting city $k_i$ and city $n+1$ with a cost of $w_i$, i.e., $\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j)$.

Since the answer can be very large, you only need to output the result modulo $998244353$.

The proposals are independent of each other, meaning that all proposals do not affect the existing roads, and these proposals are not actually implemented.

Input

The first line contains two integers $n$ and $q$.

The next $n-1$ lines each contain three integers $u_i, v_i, c_i$, representing a bidirectional road connecting city $u_i$ and city $v_i$ with a cost of $c_i$.

The next $q$ lines each contain two integers $k_i, w_i$, representing a proposal for a new road.

Output

Output $q$ lines, each containing an integer. The $i$-th line represents the sum of all $cost(i,j)$ modulo $998244353$ after adding a bidirectional road connecting city $k_i$ and city $n+1$ with a cost of $w_i$, i.e., $\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j) \bmod 998244353$.

Examples

Input 1

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

Output 1

100
88

Note 1

After adding a bidirectional road connecting city $1$ and city $5$ with a cost of $2$, the roads in country F are as shown in the figure below:

For example, at this time $cost(4,5)=9$ and $cost(1,3)=5$.

It is easy to calculate that $\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j)=100$.

Input 2

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

Output 2

1050
1054
970
1148
896

Note 3

See city/city3.in and city/city3.ans in the additional files. This sample satisfies the constraints of test case 4.

Note 4

See city/city4.in and city/city4.ans in the additional files. This sample satisfies the constraints of test case 11.

Note 5

See city/city5.in and city/city5.ans in the additional files. This sample satisfies the constraints of test case 14.

Note 6

See city/city6.in and city/city6.ans in the additional files. This sample satisfies the constraints of test case 20.

Constraints

For $100\%$ of the data, $2 \le n \le 2\times10^5$, $1 \le q \le 2\times10^5$, $1 \le u_i, v_i, k_i \le n$, $1 \le c_i, w_i \le 10^6$. It is guaranteed that one can travel from any city to any other city using the original $n-1$ bidirectional roads.

Special Property A: It is guaranteed that for all $1 \le i < n$, $u_i=i, v_i=i+1$.

Special Property B: It is guaranteed that for all $1 \le i \le q$, $k_i=1$.