Problem Background

A child's dream is the most fragile thing, and even if left unattended, it will eventually shatter on its own. Therefore, it must be protected by someone.

Problem Description

"One-Eyed Small Treasure" is the favorite toy of Toxique, and as Liyue's best toy salesperson, Tartaglia has recruited \( N \) dealers to distribute "One-Eyed Small Treasure". These \( N \) dealers are numbered from \( 1 \) to \( N \).

Among the \( N \) dealers, \( M \) pairs of trading relationships have been formed, numbered from \( 1 \) to \( M \). The \( i \)-th trading relationship connects dealers \( u_i \) and \( v_i \). For the \( i \)-th trading relationship, when one party receives the production information of "One-Eyed Small Treasure", there is a probability of \( \frac{p_i}{q_i} \) that they will inform the other party. Formally, the dealers and their trading relationships form an undirected graph, and the data guarantees that this undirected graph is connected, without self-loops, and without multiple edges.

A group of dealers \( a_1, a_2, \cdots, a_k \) (where \( k > 2 \)) constitutes a business group if and only if there exist \( k \) different trading relationships such that the \( w \)-th relationship connects dealers \( a_w \) and \( a_{w \mod k + 1} \). Formally, a business group corresponds to \( k \) dealers and a simple cycle in their trading relationship graph. A dealer can belong to at most one business group.

Now, Tartaglia wishes to conduct tests on these dealers. He performs \( Q \) independent tests. For the \( i \)-th test, Tartaglia informs the production information of "One-Eyed Small Treasure" to dealer \( S_i \). How many dealers are expected to receive this information?

It can be proven that the expectation can always be expressed in the form of \( \frac{p}{q} \). You need to output the value of \( p \cdot q^{-1} \mod 998\ 244\ 353 \).

Input Format

The input consists of \( M + Q + 1 \) lines.

The first line contains three positive integers \( N \), \( M \), and \( Q \), representing the number of dealers, the number of trading relationships, and the number of tests, respectively.

The next \( M \) lines each contain four positive integers \( u_i \), \( v_i \), \( p_i \), and \( q_i \), indicating the dealers connected by the \( i \)-th trading relationship and the informing probability.

The next \( Q \) lines each contain one integer \( S_i \), representing the dealer informed in the \( i \)-th test.

Output Format

Output \( Q \) lines. For each query, output one line containing an integer, which is the expected value modulo \( 998\ 244\ 353 \).

Sample Input and Output

Input Sample #1

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

Output Sample #1

565671802

Input Sample #2

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

Output Sample #2

35936800
46584741
380663851
584039500
757135070

Input Sample #3

See the tartaglia/tartaglia3.in and tartaglia/tartaglia3.ans files in the contestant directory.

Output Sample #3

This sample meets the restrictions of test points 1 ∼ 2.

Input Sample #4

See the tartaglia/tartaglia4.in and tartaglia/tartaglia4.ans files in the contestant directory.

Output Sample #4

This sample meets the restrictions of test points 10 ∼ 13.

Input Sample #5

See the tartaglia/tartaglia5.in and tartaglia/tartaglia5.ans files in the contestant directory.

Output Sample #5

This sample meets the restrictions of test points 14 ∼ 19.

Input Sample #6

See the tartaglia/tartaglia6.in and tartaglia/tartaglia6.ans files in the contestant directory.

Output Sample #6

Notes

Sample Explanation 1

The above images show all 16 possible connected graph scenarios, numbered from 1 to 16 from top to bottom and left to right. For the query about node 1, we calculate the number of nodes reachable from node 1 and the corresponding probability for each of the 16 scenarios:

Summing up, we get \( E = \sum E_i = \frac{59}{30} \equiv 565\ 671\ 802 \pmod{998\ 244\ 353} \).

Subtasks

For all test data, it is guaranteed that \( 1 \leq N, M, Q \leq 3 \times 10^5 \), \( 1 \le u_i, v_i \le N \), \( u_i \neq v_i \), \( 1 \le p_i, q_i < 998\ 244\ 353 \), \( 1 \le S_i \le N \).

Special Property A: No business groups exist.

Special Property B: There is exactly one business group.

Hints

In this problem, you may need to use a large stack space. During the final testing, the stack space memory limit for the program is the same as the memory limit for the problem.

If you are using a Linux system, you can use the command ulimit -s unlimited to remove the system stack space limit. If you are using a Windows system, you can add -Wl,--stack=1024000000 to the compilation command to modify the system stack space limit to approximately 1024MiB.

见题面 Input 部分

见题面 Output 部分