{"raw_statement":[{"iden":"background","content":"孩童时期的梦是最易碎的东西，哪怕放着不管，也总有一天会自己碎掉，所以，一定要有人来保护才行吧。"},{"iden":"statement","content":"“独眼小宝”是托克最喜欢的玩具，作为璃月最好的玩具销售员，达达利亚共招募了 $N$ 位经销商负责分销“独眼小宝”，$N$ 位经销商依次编号为 $1,2,\\cdots,N$。\n\n$N$ 位经销商中共形成了 $M$ 对交易关系，依次编号为 $1,2,\\cdots,M$，第 $i$ 对交易关系联系起经销商 $u_i,v_i$。对于第 $i$ 对交易关系，当一方获知“独眼小宝”的生产情报时，将有 $\\dfrac{p_i}{q_i}$ 的概率告知另一方。形式化地，经销商和他们之间的交易关系构成了一张无向图，**数据保证这张无向图是连通的、无自环的和无重边的。**\n\n一些经销商 $a_1,a_2,\\cdots,a_k(k>2)$ 构成**商业集团**，**当且仅当**存在 $k$ 组不同的交易关系，使得第 $w$ 组关系联系起经销商 $a_w,a_{w \\bmod k+1}$。形式化地，一个商业集团对应 $k$ 名经销商和他们的交易关系图中的一个简单环。**一名经销商最多属于一个商业集团。**\n\n现在，达达利亚希望对这些经销商进行测试，他共进行了 $Q$ 次**独立的**测试。对于第 $i$ 次测试，达达利亚将“独眼小宝”的生产情报告知了经销商 $S_i$，请问期望条件下，共有多少名经销商会得知该情报？\n\n**可以证明，期望一定可以被表示为 $\\dfrac{p}{q}$ 的形式，你需要输出 $p\\cdot q^{-1}\\pmod {998\\ 244\\ 353}$ 的值。**"},{"iden":"input","content":"输入共 $M+Q+1$ 行。\n\n输入的第一行为三个正整数 $N,M,Q$，分别表示经销商数量、交易关系数量和测试次数。\n\n接下来 $M$ 行，每行四个正整数 $u_i,v_i,p_i,q_i$，表示第 $i$ 条交易关系联系的经销商与告知概率。\n\n接下来 $Q$ 行，每行一个整数 $S_i$，表示第 $i$ 次测试所告知的经销商。"},{"iden":"output","content":"输出 $Q$ 行。对于每组询问，输出一行一个整数，表示期望对 $998\\ 244\\ 353$ 取模的结果。"},{"iden":"note","content":"### 样例解释 1\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/ii4noq6d.png)\n![](https://cdn.luogu.com.cn/upload/image_hosting/qz2o6jfu.png)\n![](https://cdn.luogu.com.cn/upload/image_hosting/dbojsfej.png)\n![](https://cdn.luogu.com.cn/upload/image_hosting/xq08n2l2.png)\n\n上图展现了所有的 $16$ 种可能的图连通情况，从上至下，从左至右，依次编号为 $1\\sim 16$。对于节点 $1$ 的询问，我们依次计算 $16$ 种情况中节点 $1$ 能到达的节点数和该情况对应的概率：\n\n| 图编号 | 节点数 | 概率 | 期望 |\n| :--: | :--: | :--: | :--: |\n| $1$ | $4$ | $\\frac{1}{60}$ | $\\frac{1}{15}$ |\n| $2$ | $1$ | $\\frac{1}{60}$ | $\\frac{1}{60}$ |\n| $3$ | $4$ | $\\frac{1}{30}$ | $\\frac{2}{15}$ |\n| $4$ | $4$ | $\\frac{1}{15}$ | $\\frac{4}{15}$ |\n| $5$ | $4$ | $\\frac{1}{60}$ | $\\frac{1}{15}$ |\n| $6$ | $1$ | $\\frac{1}{30}$ | $\\frac{1}{30}$ |\n| $7$ | $1$ | $\\frac{1}{15}$ | $\\frac{1}{15}$ |\n| $8$ | $1$ | $\\frac{1}{60}$ | $\\frac{1}{60}$ |\n| $9$ | $3$ | $\\frac{2}{15}$ | $\\frac{2}{5}$ |\n| $10$ | $2$ | $\\frac{1}{30}$ | $\\frac{1}{15}$ |\n| $11$ | $3$ | $\\frac{1}{15}$ | $\\frac{1}{5}$ |\n| $12$ | $1$ | $\\frac{2}{15}$ | $\\frac{2}{15}$ |\n| $13$ | $1$ | $\\frac{1}{30}$ | $\\frac{1}{30}$ |\n| $14$ | $1$ | $\\frac{1}{15}$ | $\\frac{1}{15}$ |\n| $15$ | $2$ | $\\frac{2}{15}$ | $\\frac{4}{15}$ |\n| $16$ | $1$ | $\\frac{2}{15}$ | $\\frac{2}{15}$ |\n\n求和，得到 $E=\\sum E_i=\\frac{59}{30}\\equiv 565\\ 671\\ 802\\pmod{998\\ 244\\ 353}$。\n\n### 子任务\n\n对于所有测试数据，保证 $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$。\n\n| 测试点编号 | $N,M,Q\\le$ | 特殊性质 |\n| :--: | :--: | :--: |\n| $1\\sim 2$ | $17$ | 无 |\n| $3\\sim 4$ | $2\\times 10^3$ | A |\n| $5\\sim 7$ | $2\\times 10^3$ | B |\n| $8\\sim 9$ | $2\\times 10^3$ | 无 |\n| $10\\sim 13$ | $3\\times 10^5$ | A |\n| $14\\sim 19$ | $3\\times 10^5$ | B |\n| $20\\sim 25$ | $3\\times 10^5$ | 无 |\n\n特殊性质 A：不存在集团。\n\n特殊性质 B：有且只有一个集团。\n\n### 提示\n\n在本题中，你可能需要使用较大的栈空间。在最终测试时，程序可使用的栈空间内存限制与题目内存限制一致。\n\n若你使用 Linux 系统，可使用命令 `ulimit -s unlimited` 解除系统栈空间限制。若你使用 Windows 系统，可在编译命令后添加 `-Wl,--stack=1024000000`，以将系统栈空间限制修改为约 1024MiB。"}],"translated_statement":null,"sample_group":[["4 4 1\n1 2 1 2\n3 2 1 3\n3 4 1 5\n2 4 1 2\n1","565671802"],["9 9 5\n9 3 3 5\n9 1 1 2\n9 2 1 1\n4 7 4 5\n2 4 2 3\n6 8 1 4\n5 6 1 3\n3 5 2 5\n8 3 3 5\n1\n3\n4\n7\n5","35936800\n46584741\n380663851\n584039500\n757135070"],["见选手目录下的 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。",""]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}