杀蚂蚁（antbusters）是一款风靡 OI 界的游戏，下面介绍它的一个简单版本。

游戏的地图是一棵 $n$ 个节点的树，其中 $1$ 号点时蚂蚁窝，并且 $1$ 号点只与 $2$ 号点直接相连。

现在有一只蚂蚁拿着蛋糕从树上某个节点 $s$ 出发，按照如下规则随机游走：

1. 树上每一个节点 $i$ 都有一定数量的信息素 $v_i$。
2. 如果蚂蚁当前位于节点 $x$，与 $x$ 相邻的节点分别为 $y_1, y_2, \cdots, y_r$，那么蚂蚁下一步走到节点 $y_i$（$1 \leq i \leq r$）的概率是 $\displaystyle \frac{v_{y_i}}{\sum_{k=1}^r v_{y_k}}$。
3. 如果蚂蚁在某一步移动结束后位于 $1$ 号点（蚂蚁窝），游戏结束。

现在你有一个攻击装置，这个攻击装置的工作原理是：

1. 游戏开始时，你需要选择树上的一条简单路径，这个路径就是该装置的攻击范围，在之后的游戏进程中你不可以改变它。
2. 之后在每秒初，如果蚂蚁在这条路径上，则蚂蚁就会被攻击而受到 $1$ 点伤害。

你现在要进行 $q$ 次游戏，每次游戏会给定蚂蚁出生点 $s$，你想知道，如果在这次游戏中选择 $x$ 号点到 $y$ 号点这条简单路径作为攻击范围，在游戏结束时你对蚂蚁造成伤害的期望值是多少，由于答案非常大而且可能是个分数，你只需要输出答案对 $998\,244\,353$ 取模的结果。（如果答案化成最简分数是 $\displaystyle \frac xy$，那么你要输出 $x \times y^{-1} \bmod 998\,244\,353$ 的值，其中 $y^{-1}$ 是 $y$ 在模 $998\,244\,353$ 意义下的逆元）。

这里假设蚂蚁的血量是无限的，这意味着蚂蚁走到 $1$ 号点时游戏才会结束。

输入格式

第一行，一个整数 $n$，表示树的节点数。

接下来一行，有 $n$ 个正整数，第 $i$ 个整数表示 $v_i$，含义如题面所示。

接下来 $n-1$ 行，每行两个整数 $u, v$，表示树上的一条连接 $u$ 号点和 $v$ 号点的边。

接下来一行，一个整数 $q$，表示询问次数。

接下来 $q$ 行，每行三个整数 $s, x, y$，含义如题面所示。

输出格式

输出共 $q$ 行，每行包含一个整数，第 $i$ 行表示第 $i$ 次询问的答案。

样例数据

样例输入

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

样例输出

5

子任务

• 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): 无特殊限制

对于 $100\%$ 的数据，有 $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_i, y \leq n$，保证给出的图为一棵树，且 $1$ 号点只与 $2$ 号点直接相连。