Sum of Road Costs in F Country

In the mythical online nation F, Little C serves as president. F country consists of n cities connected by n-1 bidirectional roads, forming a tree so that any city is reachable from any other city. Each road has a fee: the i-th road costs \(c_i\) units. For two cities \(x\) and \(y\), define \(cost(x, y)\) as the sum of fees along the unique simple path connecting them (with \(cost(x,x)=0\)).

Little C has built a new city, labeled n+1, and he considers several proposals to connect it to F. In each proposal, a new road is built connecting city \(k\) and city \(n+1\) with fee \(w\). This guarantees that the new network of n+1 cities is connected. For each proposal, compute the total sum of \(cost(i,j)\) over all ordered pairs \((i, j)\), i.e.,

[ S = \sum_{i=1}^{n+1} \sum_{j=1}^{n+1} cost(i,j) \pmod{998244353}. ]

Note: Each proposal is independent, meaning the new road is considered on the original tree without affecting other proposals.

inputFormat

The input begins with an integer n (\(2 \le n \le 2 \times 10^5\)), the number of cities in F (excluding the new city). Then follow n-1 lines, each containing three integers u v c, indicating there is a bidirectional road between cities u and v with fee c (\(1 \le c \le 10^9\)). It is guaranteed that these roads form a tree.

The next line contains a single integer q (\(1 \le q \le 2 \times 10^5\)), the number of proposals. Each of the following q lines contains two integers k (\(1 \le k \le n\)) and w (\(1 \le w \le 10^9\)). For every proposal, a new road will be added connecting city k and the new city n+1 with fee w.

outputFormat

For each proposal, output the value of \(S\) modulo 998244353 on a separate line.

sample

3
1 2 1
2 3 2
2
1 1
2 3

26
36