Counting Walks in a Weighted Directed Graph

You are given a directed graph with n vertices and m edges. Each edge has an integer weight. There are also q queries. Each query is in the form: given vertices u and v and a target weight w, how many walks from u to v have a total weight exactly w? A walk is allowed to visit vertices and edges multiple times. Since the answers can be large, output the result modulo P (i.e. the remainder when divided by P).

The input consists of multiple test cases. In fact, you are given all 10 groups of inputs. In our sample, the first line of the input is an integer T (for example, T = 3 representing 3 combined test cases). For each test case, the first line contains four integers n, m, q and P. Then follow m lines, each containing three integers u, v and w, representing a directed edge from vertex u to vertex v with weight w. Finally, there are q lines, each with three integers u, v and w, representing a query.

The task is to compute, for each query, the number of walks from u to v with total weight exactly w, modulo $$P$$.

inputFormat

The input begins with an integer T indicating the number of test cases.

T
For each test case:
n m q P
u1 v1 w1
u2 v2 w2
... (m edges)
u1' v1' w1'
u2' v2' w2'
... (q queries)

All numbers are integers. Vertices are numbered starting from 1.

outputFormat

For each test case, output q lines. The i-th line should contain a single integer representing the number of walks for the i-th query, modulo P.

sample

3
2 2 2 1000000007
1 2 1
2 1 1
1 1 2
1 2 1
3 3 2 100
1 2 2
2 3 2
1 3 5
1 3 4
1 3 5
3 4 3 13
1 1 1
1 2 2
2 3 3
3 1 4
1 1 3
1 3 9
2 2 7

1
1
1
1
1
1
0