問題文
冒险者 Platypus 小伙和 Qlatyqus 小伙正在攻略分布在巨大平原上的地下城。
2 人 N 他们进行了为期 日的冒险,1 每一天,Platypus 小伙或 Qlatyqus 小伙会攻略某个地点的地下城。
具体来说,i 日目 (1\leq i \leq N) 有 A_i 是
在 P 的时候是 Platypus 小伙,而 A_i 是
在 Q 的时候是 Qlatyqus 小伙,在坐标 (X_i, Y_i) 的地下城。在这里,X_i,Y_i 是整数。
为了攻略尽可能广范围的地下城,
为了尽可能攻略更广范围的地下城,2 从人们应该尽可能合作的角度来看,i 第几天时的 2 对人的奖励金 S_i 定义如下。
- Platypus 小朋友在 i 第几天之前攻略的某个地下城的分数,以及 Qlatyqus 小朋友的 i 日目之前攻略的某个地下城的点,2 考虑取这些点中点的操作。通过此操作得到的所有中点的集合, M 。M 的点全都包含在内的凸多边形中,其面积最小的面积称为 S_i 。但是,如果存在可以任意小的凸多边形面积,S_i=0 。
Platypus 和 Qlatyqus 想要1 计算每天的奖励金是多少。他们的 N 地下城攻略信息在这些天内被提供,i 第几天时的 2 对人的奖励金 S_i 该值应乘以 1 请制作一个按天报告的程序。不过,所求的值可以被证明是有理数,正如注释中所述, \bmod 998244353 请输出。
出力方法
输出有理数时,需首先将该有理数用分数表示 \frac p q 。在这里,p, q 是一个整数并且q 是
您也可以写 998244353 不能被整除(在此问题的约束下,这种表示总是可能的)。然后, p\equiv qr\pmod{998244353} 输出有多少个 0 以上 998244353 输出小于该分数的唯一整数 r 请输出。
制約
- 1 \leq N \leq 2 \times 10^5
- X_i, Y_i 是一个整数,0 \leq X_i, Y_i \lt 998244353 \ (1 \leq i \leq N) 小于
- A_i 是一个字符
P或Q任何一个 - i \neq j 和 A_i = A_j 如果 (X_i, Y_i) \neq (X_j, Y_j)
入力
输入是按以下格式从标准输入给出的。
N A_1 X_1 Y_1 \vdots A_N X_N Y_N
出力
N 行。i 行中, i 每天的奖励金值 S_i 按照输出方法进行输出。
入力例1
5 P 0 1 Q 1 0 P 2 1 Q 1 2 Q 2 2
出力例1
0 0 0 1 748683266
- 1 第 N 天 Platypus 在坐标 (0,1) 的地城。由于 Qlatyqus 还没有攻略过任何地城,所以奖励金在 0 。
- 2 日时,Qlatyqus 将攻略位于 (1,0) 的地城。通过初日攻略的地城与 2 日攻略的地城的中点,可以取包含 \left(\frac{1}{2},\frac{1}{2}\right) 但是, 不是1 点的任意小的凸多边形,因此奖励金仍然是 0 。
- 出于同样的原因, 3 第一天的奖金是 0 。
- 4 到第二天时,如下图所示,紫色表示的点表示中点的集合 M ,紫色多边形表示 M 所包含的凸多边形。
因此奖金是 1 。 对于
4 到第几天为止的地下城攻略情况(蓝点表示 Platypus 君,红点表示 Qlatyqus 君攻略的地下城位置)
- 最终日中点的集合 M 与凸多边形如下图所示。
因此奖金是 \frac{5}{4} 如下。请注意输出方法。
最终的地下城攻略状况
入力例2
8 P 0 0 Q 0 0 P 0 998244352 Q 0 998244352 P 998244352 0 Q 998244352 0 P 998244352 998244352 Q 998244352 998244352
出力例2
0 0 0 0 623902721 499122177 124780545 1