At the NOIP 2044 competition, Little D encountered the following problem:
Given a graph with $n$ vertices and $m$ weighted directed edges, there are $q$ queries. Each query asks for the number of paths from vertex $u$ to vertex $v$ with a total length of $w$. You only need to output the answer modulo $P$.
Little D thought about this problem for a long time but could not solve it. After leaving the competition, he obtained the data for this problem from the official website, which consists of 10 test cases. Little D really wants to solve this problem, so he has asked for your help and provided you with the input for the 10 test cases. As a clever programmer, you will surely be able to calculate the output for each test case!
Input
The input files noip1.in through noip10.in are already provided in the download files.
The first line of each input file contains 4 positive integers $n, m, q, P$, representing the number of vertices, the number of edges, the number of queries, and the modulus, respectively. The vertices are numbered from $1$ to $n$.
The next $m$ lines each describe one of the $m$ weighted directed edges. The $i$-th line contains 3 integers $a_i, b_i, c_i$, indicating that the $i$-th edge starts at $a_i$, ends at $b_i$, and has a weight of $c_i$.
The next $q$ lines describe the queries. The $k$-th line contains 3 integers $u_k, v_k, w_k$, indicating that the $k$-th query requires the number of paths from vertex $u_k$ to vertex $v_k$ with length $w_k$, modulo $P$.
Output
The output files are noip1.out through noip10.out, corresponding to the respective input files.
Each output file should contain no more than $q$ lines, with each line containing a non-negative integer less than $P$, representing the answer to the corresponding query for that test case.
Examples
Input 1
3 4 2 10 1 1 2 1 3 1 2 3 3 1 3 5 1 3 3
Output 1
2 1
Note
For the first query, there are two paths from vertex $1$ to vertex $3$ with length $5$. Assuming the edges are numbered from $1$ to $4$, the edges traversed by these two paths are:
Path 1: $2 \rightarrow 4$
Path 2: $1 \rightarrow 1 \rightarrow 3$.
Additional Examples
We have provided noip1.sampleout through noip10.sampleout, which correspond to the correct output for the first query of each test case.
Subtasks
Each test case is scored individually. You may receive partial points for each test case.
During the final evaluation, we will calculate your score based on the number of queries you answered correctly for each data set.
If your output contains no more than $q$ lines, and each line contains only a non-negative integer not exceeding $P$, we will assume during the final evaluation that your output on line $i$ is the answer to the $i$-th query of the corresponding test case.
For each test case, we have set 10 scoring parameters $a_1, a_2, \dots, a_{10}$. In your solution, if the number of correctly answered queries is $w_{\mathrm{user}}$, your score will be given by the table below (if multiple conditions are met, the highest score is taken):
| Score | Condition | Score | Condition |
|---|---|---|---|
| $10$ | $w_{\mathrm{user}} \geq a_{10}$ | $5$ | $w_{\mathrm{user}} \geq a_{5}$ |
| $9$ | $w_{\mathrm{user}} \geq a_{9}$ | $4$ | $w_{\mathrm{user}} \geq a_{4}$ |
| $8$ | $w_{\mathrm{user}} \geq a_{8}$ | $3$ | $w_{\mathrm{user}} \geq a_{3}$ |
| $7$ | $w_{\mathrm{user}} \geq a_{7}$ | $2$ | $w_{\mathrm{user}} \geq a_{2}$ |
| $6$ | $w_{\mathrm{user}} \geq a_{6}$ | $1$ | $w_{\mathrm{user}} \geq a_{1}$ |
If your output does not meet the format requirements, such as containing integers not less than $P$, negative numbers, or exceeding $q$ lines, we do not guarantee that you will receive any points.
The scoring parameter file noip.score is already in the problem directory. This file contains 10 lines, where the $i$-th line describes the scoring parameters for test case $i$. Each line contains 10 integers, representing $a_1, a_2, \dots, a_{10}$ in order.
Note
Knowledge that may be useful for this problem:
Characteristic Polynomial: For an $n \times n$ matrix $A$, the characteristic polynomial $f(\lambda) = \det(\lambda I - A)$ is an $n$-th degree polynomial in $\lambda$, where $I$ is the $n \times n$ identity matrix and $\det$ is the determinant. $f(\lambda)$ is called the characteristic polynomial of $A$.
Cayley-Hamilton Theorem: For the characteristic polynomial $f(\lambda)$ of a square matrix $A$, it is always true that $f(A) = 0$. That is, substituting the matrix itself as the variable into the characteristic polynomial results in the zero matrix.