AT_utpc2020_m Not Another Geometry Game!

冒险者 Platypus 君和 Qlatyqus 君正在探索一片广阔的平原，他们一天一个地点，轮流挑战多个分散的地牢。总共的冒险天数为 $N$ 天。在第 $i$ 天 $(1 \leq i \leq N)$，如果 $A_i$ 为 `P`，则表示当天由 Platypus 君前往坐标 $(X_i, Y_i)$ 的地牢挑战；如果 $A_i$ 为 `Q`，则当天由 Qlatyqus 君前往同样坐标的地牢挑战，$X_i, Y_i$ 为整数。 为了鼓励两人协作，他们每天获得的奖金 $S_i$ 由以下标准定义： - 考虑 Platypus 君和 Qlatyqus 君在第 $i$ 天之前攻略的所有地牢坐标，并计算出所有可能的中点集合 $M$。$S_i$ 是能包含所有中点的最小凸多边形面积。如果这种凸多边形的面积可以任意接近零，那么 $S_i = 0$。 他们希望每天能知道他们的奖金多少。根据 $N$ 天内的地牢攻略数据，请编写一个程序，计算并输出他们每日的奖金 $S_i$。由于结果可能是有理数，需要对 $998244353$ 取模输出。 **输出方法**：将有理数表示为分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q$ 不可被 $998244353$ 整除（在本题限制条件下，总能找到这样的表示）。求出满足 $p \equiv qr \pmod{998244353}$ 的唯一整数 $r$（$0 \leq r < 998244353$）并输出 $r$。

标准输入如下： - 第一行输入一个整数 $N$ - 接下来的 $N$ 行，每行输入三个值 $A_i$（字符 `P` 或 `Q`），$X_i$ 和 $Y_i$（两个整数）

输出 $N$ 行，第 $i$ 行表示第 $i$ 天他们的奖金 $S_i$，按之前描述的方法输出结果。 ## 数据范围 - $1 \leq N \leq 2 \times 10^5$ - $0 \leq X_i, Y_i < 998244353$ - 如果 $A_i = A_j$ 且 $i \neq j$，则 $(X_i, Y_i) \neq (X_j, Y_j)$ ### 示例解释 - 第 1 天只有 Platypus 君一个人在坐标 $(0,1)$ 攻略地牢，没有 Qlatyqus 君的地牢记录，奖金为 0。 - 第 2 天，Qlatyqus 君在坐标 $(1,0)$ 攻略地牢，虽然有了中点 $\left(\frac{1}{2},\frac{1}{2}\right)$，但只有一个中点点，不足以形成有限面积的凸多边形，因此奖金依旧为 0。 - 第 3 天经过类似操作，奖金依旧为 0。 - 第 4 天，构成了如图所示的中点集合 $M$，使得形成一个面积为 1 的凸多边形，所以奖金为 1。 - 最终的中点集合 $M$ 以及相应的凸多边形如图所示，奖金为 $\frac{5}{4}$。根据输出要求进行取模计算。 **本翻译由 AI 自动生成**

### 制約 - $ 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} $ となります。出力方法に注意してください。