为了出题，出题人 03 喜欢在校园里闲逛。

校园可以看成抽象成是一张 $n$ 个点 $m$ 条边的有向图，第 $i$ 条边从 $a_i$ 连向 $b_i$，边权为 $c_i$。

出题人 03 总共会闲逛 $Q$ 天，在第 $i$ 天，他会从 $x_i$ 出发，到达 $y_i$，同时希望自己走过的路径边权和恰好为 $v_i$。

出题人 03 很好奇，每一天他可以有多少种不同的路径呢? 由于答案很大，你只需要回答答案对 $998244353$ 取模的结果。

同一条路径可以多次经过同一条边。两条路径相同当且仅当两条路径上的边数相同且边的编号依次相等。

输入格式

第一行四个整数 $n,m,Q,\underset{v}{max}$。

接下来 $m$ 行，每行三个正整数表示 $a_i,b_i,c_i$。

接下来 $Q$ 行，每行三个正整数表示 $x_i,y_i,v_i$。

输出格式

$Q$ 行，第 $i$ 行一个整数表示第 $i$ 次询问的答案对 $998244353$ 取模的结果。

样例一

input

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

output

3
4
6
8
19

explanation

在第一天中，存在如下三条闲逛路径：（$\mathrm{\#}i$ 表示输入数据中第 $i$ 条边）

$1\stackrel{\mathrm{\#}1}{\to }2\stackrel{\mathrm{\#}4}{\to }3$

$1\stackrel{\mathrm{\#}1}{\to }2\stackrel{\mathrm{\#}7}{\to }1\stackrel{\mathrm{\#}1}{\to }2\stackrel{\mathrm{\#}2}{\to }3$

$1\stackrel{\mathrm{\#}1}{\to }2\stackrel{\mathrm{\#}7}{\to }1\stackrel{\mathrm{\#}10}{\to }3$

注意一条路径可以重复经过一个点，也可以重复经过一条边。

样例二

见附加文件。

该测试点$n=3$，其余范围同测试点$1$。

数据范围

对于所有测试点，满足 $1\le n\le 8,0\le m\le 300000,1\le \underset{v}{max}\le 65000,0\le Q\le 10000$。

对于所有测试点，满足 $1\le a_i,b_i,x_i,y_i\le n,1\le c_i,v_i\le \underset{v}{max}$。

请注意选手程序自身常数因子对程序运行时间带来的影响

时间限制：$4\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载