该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

昆明的雨Ⅲ

题目背景

雨季的果子，是杨梅。卖杨梅的都是苗族女孩子，戴一顶小花帽子，穿着扳尖的绣了满帮花的鞋，坐在人家阶石的一角，不时吆唤一声：“卖杨梅——”声音娇娇的。她们的声音使得昆明雨季的空气更加柔和了。昆明的杨梅很大，有一个乒乓球那样大，颜色黑红黑红的，叫作“火炭梅”。这个名字起得真好，真是像一球烧得炽红的火炭!一点都不酸!我吃过苏州洞庭山的杨梅、井冈山的杨梅，好像都比不上昆明的火炭梅。

题目描述

今天 $wqsing$ 发现了一颗杨梅树，共 $n$ 个点。

每个树节点生长着一个杨梅，结点 $i$ 的杨梅重量为 $w_i$ 。

$wqsing$ 总共只能摘下总重量不超过 $m$ 的杨梅。

这时 $sad$ 出现了，$sad$ 向 $wqsing$ 询问了 $q$ 个问题，

每次询问为 : 如果只能摘下从点 $1$ 到点 $x$ 的简单路径上的杨梅，并且不能摘下点 $y$ 处的杨梅，总共有多少种摘下杨梅的方案。

注意：不摘下任何杨梅也是一种方案；数据不保证点 $y$ 一定在点 $1$ 到点 $x$ 的简单路径上。

方案数可能很大，请输出方案数模 $998244353$ 之后的结果。

输入格式

前一行 $2$ 个数 $n,m$

接下来一行输入 $w_1, w_2, w_3, ... , w_n$

接下来 $n - 1$ 行，每行输入 $u,v$，表示一条无向边连接 $u,v$

接下来一行输入 $1$ 个数 $q$

接下来 $q$ 行，每行输入 $x,y$，询问如果只能摘下从点 $1$ 到点 $x$ 的简单路径上的杨梅，并且不能摘下点 $y$ 处的杨梅，总共有多少种摘下杨梅的方案

输出格式

输出 $q$ 行，对于每个询问，输出摘下杨梅的方案数

样例 #1

样例输入 #1

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

样例输出 #1

2
3
7
4

样例 #2

样例输入 #2

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

样例输出 #2

8
44
47
4
47
25
8
4
8
8

提示

样例1说明

对于询问 $2,1$ : 可选的集合为 $\{\},\{2\}$，重量分别为 $0,7$

对于询问 $4,6$ : 可选的集合为 $\{\},\{1\},\{4\}$ ，重量分别为 $0,2,10$

对于询问 $5,2$ : 可选的集合为 $\{\},\{1\}, \{3\},\{5\},\{1,3\},\{1, 5\},\{3, 5\}$ ，重量分别为 $0,2,5,4,7,6,9$

对于询问 $5,3$ : 可选的集合为 $\{\},\{1\},\{5\},\{1,5\}$ ，重量分别为 $0,2,4,6$

数据范围

对于 $100\%$ 数据 $2 \le n,m,q \le 5000, 1 \le w_i \le m, 1\le x,y \le n$ 。