问题描述
在Byteland一共有$n$个城市，编号依次为$1$到$n$，同时有$m$条单向道路连接着这些城市，其中第$i$条道路的起点为$u_i$，终点为$v_i(1\leq u_i < v_i\leq n)$。
特工团队一共有$3$名成员：007，008，以及009，他们将要执行$q$次秘密任务。
在每次任务中，三人可能会处于三个不同的城市，他们互相之间通过对讲机保持联络。编号为$i$的城市的无线电频为$w_i$，如果两个城市的无线电频差值的绝对值不超过$K$，那么无线电就可以接通。三个特工每个时刻必须要选择一条道路，走到下一个城市，每条道路都只需要花费$1$单位时间。
他们可以选择在任意城市终止任务，甚至可以在起点就终止任务，但不允许在道路上终止任务。现在他们想知道，对于每次任务，给定三个人的起始位置，有多少种可能的合法行动方案，使得行动过程中任意在城市的时刻，他们都可以两两联络？
两个方案被视作不同当且仅当至少存在一个人在某一时刻所在的城市不同。
注意：$3$个特工必须同时结束任务。
输入描述
输入的第一行包含一个正整数$T(1\leq T\leq 10)$，表示测试数据的组数。
对于每组数据，第一行包含四个整数$n(1\leq n\leq 50),m(0\leq m\leq \frac{n(n-1)}{2}),K(0\leq K\leq 10^9),q(1\leq q\leq 125000)$，表示城市数，道路数，允许的差值上限以及任务个数。
第二行包含$n$个正整数$w_i(1\leq w_i\leq 10^9)$，依次表示每个城市的无线电频。
接下来$m$行，每行包含两个正整数$u_i,v_i(1\leq u_i < v_i\leq n)$，表示一条单向道路，数据保证没有重边。
接下来$q$行，每行包含三个正整数$x,y,z(1\leq x,y,z\leq n)$，表示一次任务中三个人的起始位置。数据保证在起始位置三个人可以两两联络。
输出描述
对于每组数据，输出$q$行，对于每个任务输出方案数。由于答案可能很大，请对$998244353$取模。
输入样例
1
4 4 2 10
8 8 4 1
1 3
1 4
2 3
2 4
1 1 1
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1
2 2 2
3 3 3
4 4 4
输出样例
3
3
3
3
3
3
3
3
1
1
