Antbusters is a popular game in the OI community. Below is a simplified version of the game.

The game map is a tree with $n$ nodes, where node $1$ is the ant nest, and node $1$ is connected only to node $2$.

An ant carrying a cake starts at some node $s$ on the tree and performs a random walk according to the following rules:

1. Each node $i$ on the tree has a certain amount of pheromones $v_i$.
2. If the ant is currently at node $x$, and the nodes adjacent to $x$ are $y_1, y_2, \dots, y_r$, the probability that the ant moves to node $y_i$ ($1 \leq i \leq r$) in the next step is $\displaystyle \frac{v_{y_i}}{\sum_{k=1}^r v_{y_k}}$.
3. If the ant is at node $1$ (the ant nest) after any move, the game ends.

You have an attack device that works as follows:

1. At the start of the game, you must choose a simple path on the tree, which serves as the attack range of the device. You cannot change this path during the game.
2. At the beginning of each second, if the ant is on this path, it is attacked and takes $1$ point of damage.

You are to play $q$ games. For each game, you are given the ant's starting node $s$. You want to know the expected total damage dealt to the ant by the end of the game if you choose the simple path between node $x$ and node $y$ as the attack range. Since the answer can be very large and may be a fraction, you only need to output the result modulo $998\,244\,353$. (If the answer in simplest form is $\displaystyle \frac xy$, you should output $x \times y^{-1} \bmod 998\,244\,353$, where $y^{-1}$ is the modular multiplicative inverse of $y$ modulo $998\,244\,353$).

Assume the ant has infinite health, meaning the game only ends when the ant reaches node $1$.

Input

The first line contains an integer $n$, the number of nodes in the tree.

The next line contains $n$ positive integers, where the $i$-th integer represents $v_i$, as described in the problem.

The next $n-1$ lines each contain two integers $u, v$, representing an edge between node $u$ and node $v$.

The next line contains an integer $q$, the number of queries.

The next $q$ lines each contain three integers $s, x, y$, as described in the problem.

Output

Output $q$ lines, each containing an integer representing the answer to the $i$-th query.

Examples

Input 1

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

Output 1

5

Subtasks

• Subtask 1 (10 pts): $n \leq 5$, $v_i = 1$, $q = 1$, $s = 2$.
• Subtask 2 (10 pts): $n \leq 100$, $s = 2$.
• Subtask 3 (15 pts): $v = u + 1$, $s = 2$.
• Subtask 4 (15 pts): $v = u + 1$.
• Subtask 5 (20 pts): $s = 2$.
• Subtask 6 (30 pts): No special restrictions.

For $100\%$ of the data, $n \leq 10^5$, $q \leq 10^5$, $\sum_{i=1}^n v_i < 998\,244\,353$, $v_i \geq 1$, $2 \leq s, x, y \leq n$. It is guaranteed that the given graph is a tree and node $1$ is connected only to node $2$.