Matrix Elimination Query

Before parting, little M left a note for little K:

If you can finish what I started, there is a chance we may meet again.

We define an infinite matrix \(A\) with

\(A_{i,j} = i\,j\,\gcd(i,j)\)

There are \(m\) operations. Each operation is given in one line with 1 to 3 integers. Their meanings are as follows:

• 1 : Perform Gaussian elimination on the matrix \(A\) so that it becomes an upper triangular matrix.
• 2 x y : Query the current value of \(A_{x,y}\).
• 3 x : Query \(\sum_{i=1}^{x}\sum_{j=1}^{x}A_{i,j}\) in the current matrix.
• 4 x : Let \(B\) be the \(x\times x\) matrix with \(B_{i,j}=A_{i,j}\). Compute \(\det B\). Note that if you are not familiar with determinants, please refer here.

Important: In Gaussian elimination (operation 1) the only allowed operation is to add an integer multiple of one row to another row. You are not allowed to swap two rows or multiply a row by a non-unit value. This guarantees that after elimination, the matrix is upper triangular and every element remains a non-negative integer.

All answers should be output modulo \(998244353\).

---

Note: Operation 1 permanently transforms the matrix \(A\) to its upper triangular form. Before elimination the value of \(A_{i,j}\) is defined as \(i\,j\,\gcd(i,j)\). After elimination the determinant of the submatrix \(B\) (of order \(x\)) is the product of the diagonal elements, that is

\(\prod_{i=1}^{x} (i^2\,\varphi(i))\)

where \(\varphi(i)\) is Euler's totient function.

inputFormat

The first line contains an integer \(m\) denoting the number of operations. Each of the following \(m\) lines contains an operation in one of the following formats:

• 1
• 2 x y
• 3 x
• 4 x

It is guaranteed that all indices \(x, y\) in the operations are positive integers and are small enough for a simulation.

outputFormat

For each operation of type 2, 3 and 4, output the answer modulo \(998244353\), each on a separate line.

sample

4
2 1 1
3 2
4 2
1

1
13
4

</p>