Background

“It’s finally… finally time to say goodbye.”

“Alright. After this time, maybe we will never meet again…”

“No matter what, we still have to part…”

“I understand you. Thank you for staying by my side these days.”

“Me too. If possible, I really wish I could keep staying with you.”

“After we part, I won’t be the me I am now…”

“At least, not like now.”

“After leaving you, I also won’t be like I am now…”

“Where are you going? Where do you want to go? Don’t go, don’t go! If you must go, please take me with you!”

…

“So… so what should we do now?”

“Then let us sing and dance in it!”

The sound of a violin and an accordion rang in my ears. It was so familiar, yet so unfamiliar…

Problem 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