Background

::::info[Concept Explanation]{open} For a positive integer $N$, define the set

$$\mathcal D(N)=\left\{\left\lfloor\frac Nd\right\rfloor:1\le d\le N\right\}$$

Sort the numbers in $\mathcal D(N)$ in increasing order as $1=d_1<d_2<\cdots<d_K=N$.

Let $F(n)=\sum_{i=1}^n f(i)$ be the prefix sum function of $f(n)$. In this problem, the block sieve of $f$ is defined as the following vector:

$$\mathbf B_f(N)=\left(F(d_1),F(d_2),\ldots,F(d_K)\right)$$

::::

Problem Description

You need to dynamically maintain the block sieve of a multiplicative function $f(x)$.

More specifically, you are initially given the range $N$ and the values of $f$ at all prime powers not exceeding $N$. Then there will be $Q$ operations, and each operation is one of the following two types:

1. Given a prime $p$, modify the point values of $f(p),f(p^2),\ldots,f(p^{\lfloor\log_p N\rfloor})$.
2. Query the block sieve of $f$.

To avoid too much output, for a “query the block sieve of $f$” operation, you only need to compute the following function:

$$S_f(N)=\bigoplus_{x\in\mathcal D(N)} x\left(F(x)\bmod 998244353\right)$$

Input Format

The first line contains two positive integers $N,Q$.

In the next $\pi(N)$ lines, in the $i$-th line there are $\lfloor\log_{p_i}N\rfloor$ integers, where the $j$-th number is $f(p_i^j)$. Here $p_i$ is the $i$-th prime in increasing order.

In the next $Q$ lines, each line contains several integers. The first integer $\textit{op}$ indicates the type of the operation:

• If $\textit{op}=1$, the next integer is the prime $p$ to be modified, followed by $\lfloor\log_pN\rfloor$ integers, which are the new values of $f(p),f(p^2),\ldots,f(p^{\lfloor\log_pN\rfloor})$ in order.
• If $\textit{op}=2$, you need to output the current value of $S_f(N)$.

Output Format

Output several lines, each containing one non-negative integer, representing the value of $S_f(N)$ for each query.

6 5
1 1
1
1
2
1 2 0 2
2
1 3 0
2

40
27
24

Hint

For $20\%$ of the testdata, $NQ \le 10^7$.
For another $30\%$ of the testdata, all operations with $\textit{op}=1$ have the same $p$.
For $100\%$ of the testdata, $2\le N\le 10^7$, $1\le Q\le 3\times10^4$, $\textit{op}\in\{1,2\}$, $2\le p\le N$ and $p$ is prime, and any given $f(p^k)$ satisfies $0\le f(p^k)<998244353$.

The time limit is about $1.5$ times the running time of std on the slowest case.

Translated by ChatGPT 5