시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 1024 MB853100.000%

## 문제

For two arrays of integers $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 colored black if $0 \le A_i + B_j$ and white otherwise.

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

In other words, $F(A, B)$ is equal to 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 each cell $(i,\, j)$ in $G(A, B)$ is colored black for all $i$, $j$ such that $l_1 \le i \le r_1$, $l_2 \le j \le r_2$.

Initially, only $A_1$ and $B_1$ are given.

Then, you should process following $Q$ queries:

• 0 $v$: append $v$ to current array $A$.
• 1 $v$: append $v$ to current array $A$. Then, print $F(A, B)\bmod 998\,244\,353$.
• 2 $v$: append $v$ to current array $B$.
• 3 $v$: append $v$ to 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 denoting the queries in the described form.

## 출력

For each query of types 1 and 3, output a single integer denoting the answer to that query. Each answer should go on its own line.

## 제한

Let $N$ be the size of array $A$ after processing all queries, and $M$ be the size of array $B$ after processing all queries.

• $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)$
• The last query has a type of 1 or 3.

## 서브태스크 1 (30점)

• $N \le 2\,500$
• $M \le 2\,500$

## 서브태스크 2 (15점)

• Every query except the last one has type of 0 or 2.

## 예제 입력 1

4
-4 -3
0 -5
2 2
0 3
3 -5


## 예제 출력 1

3


## 예제 입력 2

8
-187121777 648583176
0 536185451
1 77324177
2 -543947071
1 -495948203
2 809620127
2 918209957
3 -724806401
1 30094601


## 예제 출력 2

6
10
40
60


## 채점 및 기타 정보

• 예제는 채점하지 않는다.