#P7101. [W1] 推

[W1] 推

题目背景

一个”点集“为一个二维平面上的整点组成的多重集合。
可以从一个点集构造一个三角形当且仅当这个三角形的所有顶点在该点集里面。
从一个点集 SS 里可以构造恰好 S3|S|^3 个三角形。(可能一些三角形会退化为一条面积为 0 的线段)

题目描述

有一个点集,初始为空集。
NN 个操作,在每一个操作,会从这个点集插入或删除一个点。每一步完成后,询问这个点集可构造的所有三角形面积 八次方 之和。

所有询问答案都可以表示为 a/ba/b,其中 aabb 互质。输出 ab1(mod998244353)a\cdot b^{-1}\pmod{998244353}

输入格式

第一行一个正整数 NN,表示接下来的步骤个数。
接下来 NN 行,每一行三个正整数 t,x,yt,x,y
如果 t=1t=1,则插入 (x,y)(x,y) 这个点;如果 t=2t=2 则删除 (x,y)(x,y) 这个点。

输出格式

一共 NN 行,第 ii 行一个正整数,表示第 ii 个步骤完成之后的询问答案。

7
1 0 0
1 0 1
1 2 0
2 2 0
1 4 0
2 4 0
1 6 0
0
0
1
0
256
0
6561
5
1 0 0
1 0 1
1 1 0
1 1 1
2 0 1
0
0
994344961
982646785
994344961

提示

对于 10%10\% 的数据,N10N\le10
对于 30%30\% 的数据,N103N\le10^3
对于另外 10%10\% 的数据,没有删除步骤;
对于 100%100\% 的数据,1N105,0x,y<9982443531\le N\le10^5,0\le x,y<998244353,任何删除的点都保证原来存在。