Comet OJ

C1178 [Contest #2]情报强者追逐事件

内存限制：256 MB 时间限制：2000 ms

题目描述

作为一名情报强者，Takuru 正沉迷于追逐新世代的疯狂再临事件。但是 Takuru 同时也是碧朋学园的一名学生，他必须要做完今天的作业。由于他过于沉迷追逐事件，导致他今天的作业还差一道题没有完成。所以 Takuru 请求你帮他完成这道题。这道题内容如下：

有 $n$ 个人在睡觉，第 $i$ 个人有 $p_i$ 的概率自己醒来。

第 $i$ 个人向第 $to_i$ 个人中出卖了自己的自由，也就是说当第 $i$ 个人没有睡着时，他会有 $s_i$ 的概率去把第 $to_i$ 个人叫醒。

求最终每个人醒来的概率。

输入格式

第一行一个正整数 $n$ ($2\leqslant n \leqslant 10^5$)，表示有 $n$ 个人。

接下来 $n$ 行，每行两个正整数 $x_i$ 和 $y_i$ ($1\leqslant x_i < y_i <998244353$)，表示 $p_i = \frac{x_i}{y_i}$。

接下来一行 $n$ 个正整数 $to_i$ ($1\leqslant to_i \leqslant n$，$to_i \neq i$)，表示第 $i$ 个人醒来后会叫醒第 $to_i$ 个人。

接下来 $n$ 行，第 $i$ 行两个正整数 $a_i$ 和 $b_i$ ($1\leqslant a_i < b_i <998244353$)，表示 $s_i = \frac{a_i}{b_i}$。

输出

一行 $n$个整数，第 $i$ 个整数的值用如下方式计算：

第 $i$ 个人最终醒来的概率可以写成一个最简分数 $\frac{X}{Y}$，那么你需要输出一个整数 $p$，满足 $0\leqslant p <998244353​$ 且 $pY \equiv X \pmod {998244353}​$。保证合法的 $p$ 存在且唯一。

样例

样例输入 1

3
1 2
1 2
1 2
2 3 1
1 2
1 2
1 2

样例输出 1

343146497 343146497 343146497

样例输入 2

2
1 2
1 2
2 1
1 3
2 3

样例输出 2

665496236 83187030

提示

第二个样例的解释：

第一个人醒来有两种情况：

1. 自己醒来：为$\frac{1}{2}$。

2. 自己没醒来，且第二个人叫醒他：为$\frac{1}{2} \times \frac{1}{2} \times \frac{2}{3} = \frac{1}{6}$。

所以第一个人醒来的概率为$\frac{1}{2} + \frac{1}{6} = \frac{2}{3}$。

同理，第二个人醒来的概率为$\frac{1}{2} + \frac{1}{2} \times \frac{1}{2} \times \frac{1}{3} =\frac{7}{12}$。