M - Not Another Geometry Game! Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

問題文

冒険者の 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 日目は 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 を包含するような凸多角形を表します。
    4 日目までのダンジョンの攻略状況（青い点は Platypus くん、赤い点は Qlatyqus くんが攻略したダンジョンの位置を示している）

    よって報酬金は 1 となります。
  • 最終日の中点の集合 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