AT_utpc2020_m Not Another Geometry Game!

[problemUrl]: https://atcoder.jp/contests/utpc2020/tasks/utpc2020_m 冒険者の 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 $ を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ X_1 $ $ Y_1 $ $ \vdots $ $ A_N $ $ X_N $ $ Y_N $

$ N $ 行出力せよ。$ i $ 行目には、 $ i $ 日目時点での報酬金 $ S_i $ の値を、出力方法で示した通りに出力せよ。

### 制約 - $ 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) $ ### Sample Explanation 1 \- $ 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 $ を包含するような凸多角形を表します。 !\[\](https://img.atcoder.jp/utpc2020/7822622fa0727ca8642568287e3c15b5.png)$ 4 $ 日目までのダンジョンの攻略状況（青い点は Platypus くん、赤い点は Qlatyqus くんが攻略したダンジョンの位置を示している） よって報酬金は $ 1 $ となります。 - 最終日の中点の集合 $ M $ と凸多角形は以下の図のようになります。 !\[\](https://img.atcoder.jp/utpc2020/e468b4f4483b7e42ca797b965aff4086.png)最終的なダンジョンの攻略状況 よって報酬金は $ \frac{5}{4} $ となります。出力方法に注意してください。