Description

Before Little M left, he left Little K a note—

If you can finish what he said, there may be a chance that I will meet you again.

You are given an infinite matrix $A$, where $A_{i,j}=ij\gcd(i,j)$.

Then there are $m$ operations. Each line contains $1$ to $3$ integers, with the following meanings:

$1$: Perform Gaussian elimination on matrix $A$ to make it an upper triangular matrix.

Note: Here, in Gaussian elimination, you are only allowed to add a multiple of one row to another row. You are not allowed to swap any two rows, and you are not allowed to multiply any row by a constant. It is guaranteed that an upper triangular matrix can still be obtained in this way, and it is guaranteed that after elimination, every element of the matrix is a non-negative integer.

$2\ x\ y$: Output the current $A_{x,y}$.

$3\ x$: Output $\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{x}A_{i,j}$.

$4\ x$: Let $B$ be an $x \times x$ matrix with $B_{i,j}=A_{i,j}$. You need to output $\det B$.

All answers above are taken modulo $998244353$.

If you do not know what a determinant is, please click here. Here, $\text{det}$ means taking the determinant of a matrix.

After you finish the task that Little M gave to Little K, you can come and look at the sheet music for the violin and accordion.

Input Format

The first line contains an integer $m$.

The next $m$ lines each contain $1\sim 3$ integers, representing an operation.

Output Format

Output several lines, each being the answer modulo $998244353$.

6
4 4
2 4 4
3 4
1
2 4 4
3 4

2304
64
186
32
72

Hint

[Help and Hints]

To make it easier for contestants to test their code, this problem additionally provides two extra sample sets for contestants to use.

Sample Input 1 Sample Output 1

Sample Input 2 Sample Output 2

[Sample Explanation]

Note that the queried ranges of $x$ and $y$ are both no more than $4$, so we use the $4\times 4$ submatrix in the top-left corner of $A$ to explain. It is easy to prove that this does not cause any impact.

Before Gaussian elimination, the matrix is $\begin{pmatrix}1&2&3&4\\2&8&6&16\\3&6&27&12\\4&16&12&64\end{pmatrix}$. After Gaussian elimination, it becomes $\begin{pmatrix}1&2&3&4\\0&4&0&8\\0&0&18&0\\0&0&0&32\end{pmatrix}$.

[Constraints]

For $100\%$ of the testdata, $1 \leq m\leq 10^5$. Among all operation $3$ queries before operation $1$, $\sum x$ does not exceed $10$ times the $x$ upper bound of each test point.

It is guaranteed that operation $1$ appears at most once.

Translated by ChatGPT 5