Background

Childhood dreams are the easiest things to break. Even if you leave them alone, one day they will break by themselves. So there must be someone to protect them.

Problem Description

“One-Eyed Little Buddy” is Toke’s favorite toy. As the best toy salesman in Liyue, Tartaglia recruited $N$ dealers to distribute “One-Eyed Little Buddy”. The $N$ dealers are numbered $1,2,\cdots,N$ in order.

Among the $N$ dealers, there are $M$ trading relationships in total, numbered $1,2,\cdots,M$ in order. The $i$-th trading relationship connects dealers $u_i$ and $v_i$. For the $i$-th trading relationship, when one side learns the production information of “One-Eyed Little Buddy”, it will tell the other side with probability $\dfrac{p_i}{q_i}$. Formally, the dealers and their trading relationships form an undirected graph. The testdata guarantees that this undirected graph is connected, has no self-loops, and has no multiple edges.

Some dealers $a_1,a_2,\cdots,a_k(k>2)$ form a business group if and only if there exist $k$ distinct trading relationships such that the $w$-th relationship connects dealers $a_w$ and $a_{w \bmod k+1}$. Formally, a business group corresponds to $k$ dealers and a simple cycle in their trading-relationship graph. A dealer belongs to at most one business group.

Now, Tartaglia wants to test these dealers. He performs $Q$ independent tests in total. In the $i$-th test, Tartaglia tells the production information of “One-Eyed Little Buddy” to dealer $S_i$. Under expectation, how many dealers will learn this information in total?

It can be proven that the expectation can always be written in the form $\dfrac{p}{q}$. You need to output the value of $p\cdot q^{-1}\pmod {998\ 244\ 353}$.

Input Format

The input has $M+Q+1$ lines.

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

The next $M$ lines each contain four positive integers $u_i,v_i,p_i,q_i$, representing the dealers connected by the $i$-th trading relationship and the probability of telling.

The next $Q$ lines each contain one integer $S_i$, representing the dealer who is told in the $i$-th test.

Output Format

Output $Q$ lines. For each query, output one integer per line, representing the expected value modulo $998\ 244\ 353$.

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

565671802

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

35936800
46584741
380663851
584039500
757135070

见选手目录下的 tartaglia/tartaglia3.in 与 tartaglia/tartaglia3.ans。

该样例满足测试点 1 ∼ 2 的限制。

见选手目录下的 tartaglia/tartaglia4.in 与 tartaglia/tartaglia4.ans。

该样例满足测试点 10 ∼ 13 的限制。

见选手目录下的 tartaglia/tartaglia5.in 与 tartaglia/tartaglia5.ans。

该样例满足测试点 14 ∼ 19 的限制。

见选手目录下的 tartaglia/tartaglia6.in 与 tartaglia/tartaglia6.ans。

Hint

Sample Explanation 1

The figures above show all $16$ possible connectivity cases of the graph. From top to bottom and left to right, they are numbered $1\sim 16$ in order. For the query at node $1$, we compute, for each of the $16$ cases, the number of nodes reachable from node $1$ and the probability of that case:

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

Subtasks

For all testdata, 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 groups exist.

Special property B: There is one and only one group.

Notes

In this problem, you may need to use a larger stack space. In the final test, the stack space memory limit available to the program is the same as the problem’s memory limit.

If you are using Linux, you can use the command ulimit -s unlimited to remove the system stack space limit. If you are using Windows, you can add -Wl,--stack=1024000000 after the compile command to change the system stack space limit to about 1024 MiB.

Translated by ChatGPT 5