Counting Rectangles

For two integer arrays $A$ of size $N$ and $B$ of size $M$, we define a grid $G(A, B)$ of size $N \times M$, where cell $(i, j)$ is black if $A_i + B_j \ge 0$ and white otherwise.

We define $F(A, B)$ as the number of black rectangles inside $G(A, B)$. Each cell of $G(A, B)$ is either entirely included in or disjoint from the rectangle.

In other words, $F(A, B)$ is the number of tuples $(l_1, r_1, l_2, r_2)$ such that $1 \le l_1 \le r_1 \le N$, $1 \le l_2 \le r_2 \le M$, and every cell $(i, j)$ with $l_1 \le i \le r_1$ and $l_2 \le j \le r_2$ is black.

Initially, only $A_1$ and $B_1$ are given. Then, you process the following $Q$ queries.

• 0 $v$: append $v$ to the current array $A$.
• 1 $v$: append $v$ to the current array $A$. Then, print $F(A, B) \bmod 998\,244\,353$.
• 2 $v$: append $v$ to the current array $B$.
• 3 $v$: append $v$ to the current array $B$. Then, print $F(A, B) \bmod 998\,244\,353$.

The first line contains one integer $Q$.

The second line contains two space-separated integers $A_1$ and $B_1$.

Each of the following $Q$ lines contains two space-separated integers, which describe a query in the form above.

For each query of type 1 or 3, print a single integer, the answer to that query, on its own line.

• $1 \le N \le 250\,000$
• $1 \le M \le 250\,000$
• $1 \le Q = N + M - 2$
• $-10^9 \le A_i \le 10^9$ ($1 \le i \le N$)
• $-10^9 \le B_i \le 10^9$ ($1 \le i \le M$)

Here $N$ is the size of array $A$ after all queries are processed, and $M$ is the size of array $B$ after all queries are processed. The last query has type 1 or 3.