Hi reader , i came across with this problem and can only solve 2 subs . Im stuck and have no idea how to solve the harder subtasks.

u re given a weighted DAG ($$$n \le 3\cdot 10^5$$$, $$$m \le 5\cdot 10^5$$$, edge weights $$$|c| \le 1000$$$) with a source $$$s$$$ and sink $$$t$$$. Whenever you reach $$$t$$$, you can jump back to $$$s$$$ with cost $$$0$$$ and start another run.

We consider a sequence of $$$D$$$ paths $$$P_1,P_2,\ldots,P_D$$$ from $$$s$$$ to $$$t$$$, where $$$D \le 10^{18}$$$. For a fixed vertex $$$v$$$, we choose exactly one of the $$$D$$$ paths that passes through $$$v$$$ to activate it.

The contribution of this sequence and activation choice is:

where $$$W(P_i)$$$ is the total weight of path $$$P_i$$$, and $$$K \le 2000$$$.

We need to calculate the answer for every vertex $$$v$$$.

Input

The first line contains four positive integers $$$n, m, K, D$$$ ($$$2 \le n \le 3 \cdot 10^5$$$, $$$1 \le m \le 5 \cdot 10^5$$$, $$$0 \le K \le 2000$$$, $$$1 \le D \le 10^18$$$).

The second line contains two positive integers $$$s, t$$$ ($$$1 \le s, t \le n$$$, $$$s \ne t$$$).

Each of the next $$$m$$$ lines contains three integers $$$u, v, c$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$, $$$|c| \le 10^3$$$), representing a directed edge from vertex $$$u$$$ to vertex $$$v$$$ with weight $$$c$$$.

Output

Print $$$n$$$ integers on a single line, where the $$$v$$$-th integer is the total energy obtained by placing a resonance station at vertex $$$v$$$, modulo $$$998244353$$$.

Subtasks:

1. $$$K=0,\ D=1$$$.

2. $$$D=1,\ K\le 50$$$.

3. $$$D\le 10^{18},\ K\le 20,\ n\le 1000$$$.

4. $$$D\le 10^{18},\ K\le 50,\ n\le 3\cdot 10^5$$$.

5. $$$D\le 10^{18},\ K\le 2000,\ n\le 3\cdot 10^5$$$.

5 6 0 1
1 5
1 4 1
4 5 1
1 2 1
2 3 1
3 5 1
1 3 1

3 1 2 1 3

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

10 3 7 10

any hints would be appreciate , thank u !