Problem Description

Xiao Lan is helping the teacher collect experimental data.

There are a total of $n$ experiments. The parameter of the $i$-th experiment is $i$, and the corresponding experimental data is $a_i$. To analyze the relationship between the experimental parameters and the experimental data, Xiao Lan needs to query the average of the experimental data in a certain continuous interval multiple times. To measure the stability of the experimental results, he also needs to query the variance of the experimental data in that interval.

In addition, Xiao Lan may redo one experiment. If the $k$-th experiment is redone, the original $a_k$ will be replaced by the new experimental data.

For a range query $[l, r]$, let the interval length be $\textit{len} = r - l + 1$, and the interval average be

$$\bar{a} = \frac{\sum_{i=l}^r a_i}{\textit{len}}.$$

In this problem, the interval variance is defined as

$$\mathrm{Var} = \sum_{i=l}^r (a_i - \bar{a})^2.$$

You need to support two types of operations:

• Query the average and variance of the interval $[l, r]$;
• Modify the experimental data at some position $k$ to $x$.

Since the answers may be rational numbers, to avoid precision errors, all query results should be output modulo $998244353$.

Specifically, suppose an answer is a rational number $x$. Write $x$ as an irreducible fraction

$$x = \frac{p}{q},$$

where $p$ and $q$ are integers, $q > 0$, and $\gcd(p, q) = 1$. This problem guarantees that $q$ is coprime with $998244353$.

Output an integer $y$ satisfying

$$\begin{aligned} 0 \le y < 998244353, y \equiv p \cdot q^{-1} \pmod{998244353}, \end{aligned}$$

where $q^{-1}$ denotes the multiplicative inverse of $q$ modulo $998244353$.

Input Format

The first line contains two positive integers $n, m$, representing the number of experiments and the number of operations.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, representing the initial experimental data.

The next $m$ lines each describe an operation in one of the following two formats:

• 1 l r: query the average and variance of the experimental data in the interval $[l, r]$;
• 2 k x: modify $a_k$ to $x$.

Output Format

For each 1 l r operation, output one line with two integers, representing the interval average and interval variance modulo $998244353$. Both results should be output according to the rational-number modulo rule described above.

4 5
1 3 2 4
1 1 3
1 2 4
2 3 5
1 1 3
1 2 4

2 2
3 2
3 8
4 2

Hint

Sample Explanation

For the first query on interval $[1, 3]$, the data are $1, 3, 2$. The average is $2$, and the variance is

$$(1 - 2)^2 + (3 - 2)^2 + (2 - 2)^2 = 2.$$

For the second query on interval $[2, 4]$, the data are $3, 2, 4$. The average is $3$, and the variance is $2$. Then $a_3$ is modified to $5$, and the sequence becomes $1, 3, 5, 4$.

For the third query on interval $[1, 3]$, the average is $3$, and the variance is $8$.

For the fourth query on interval $[2, 4]$, the average is $4$, and the variance is $2$.

Constraints and Conventions

For $50\%$ of the testdata, it is guaranteed that $n, m \le 3000$.

For another $20\%$ of the testdata, there is no operation 2 k x.

For all testdata, it is guaranteed that:

• $1 \le n, m \le 3 \times 10^5$;
• $0 \le a_i, x \le 998244353$;
• For all query operations, $1 \le l \le r \le n$;
• For all modification operations, $1 \le k \le n$.

Translated by ChatGPT 5