408152: GYM103003 D Set of Points

There is an unordered multiset $$$P$$$ of lattice points on the Cartesian plane. Initially, this multiset is empty. There are $$$N$$$ modifications, where we either add or remove a point from $$$P$$$.

Any three elements of $$$P$$$ define a triangle, possibly degenerate. After each modification, Dream wonders: what is the sum of the eighth powers of the area of the triangle that any three elements selected from $$$P$$$ without replacement define?

In other words, after each modification, calculate $$$$$$\sum_{\{A,B,C\}\subset P}S_{\triangle ABC}$$$$$$ where $$$\{A,B,C\}$$$ is a subset of $$$S$$$ of size $$$3$$$. In particular, if there are less than $$$3$$$ elements of $$$P$$$, the answer is $$$0$$$.

These subsets are unordered.

Output all answers modulo $$$998244353$$$.

Formally, let $$$M = 998244353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

The first line contains a single integer $$$N$$$ ($$$1\le N\le 10^5$$$).

Each of the next $$$N$$$ lines contains three integers $$$t$$$, $$$x$$$, and $$$y$$$ ($$$0\le x,y<998244353$$$), where $$$t$$$ is either $$$1$$$ or $$$2$$$. If $$$t=1$$$, the point $$$(x,y)$$$ is added to $$$P$$$; otherwise, the point $$$(x,y)$$$ is removed from $$$P$$$.

If $$$t=2$$$, then the test data guarantees that $$$(x,y)$$$ occurs at least once in $$$P$$$. Only one occurrence of $$$(x,y)$$$ is to be removed from $$$P$$$.

Output $$$N$$$ lines, each containing a single integer, equal to the requested value after the corresponding modification (modulo $$$998244353$$$.)

• In the zeroth subtask, worth $$$0$$$ points, the tests are the samples shown above.
• In the first subtask, worth $$$10$$$ points, $$$N\le 10$$$.
• In the second subtask, worth $$$20$$$ points, $$$N\le 10^3$$$.
• In the third subtask, worth $$$10$$$ points, $$$t=1$$$.
• In the fourth subtask, worth $$$60$$$ points, no additional restrictions are imposed.

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