题目描述

小蓝正在帮助老师统计实验数据。

一共有 $n$ 次实验，第 $i$ 次实验的参数为 $i$，对应的实验数据为 $a_i$。为了分析实验参数与实验数据之间的关系，小蓝需要多次查询某个连续区间内实验数据的平均值。为了衡量实验结果的稳定性，他还需要查询该区间内实验数据的方差。

此外，小蓝可能会重新进行某一次实验。若重新进行了第 $k$ 次实验，则原来的 $a_k$ 会被替换为新的实验数据。

对于一次区间查询 $[l, r]$，记区间长度为 $\textit{len} = r - l + 1$，区间平均值为

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

本题中，区间方差定义为

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

你需要支持两类操作：

• 查询区间 $[l, r]$ 的平均值与方差；
• 将某个位置 $k$ 的实验数据修改为 $x$。

由于答案可能是有理数，为避免精度误差，所有查询结果均在模 $998244353$ 的意义下输出。

具体地，设某个答案为有理数 $x$。将 $x$ 表示为最简分数

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

其中 $p$ 和 $q$ 为整数，$q > 0$，且 $\gcd(p, q) = 1$。本题保证 $q$ 与 $998244353$ 互质。

请输出一个整数 $y$，满足

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

这里的 $q^{-1}$ 表示 $q$ 在模 $998244353$ 意义下的乘法逆元。

输入格式

第一行包含两个正整数 $n, m$，分别表示实验次数和操作次数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示初始实验数据。

接下来 $m$ 行，每行描述一个操作，格式为以下两种之一：

• 1 l r：查询区间 $[l, r]$ 内实验数据的平均值和方差；
• 2 k x：将 $a_k$ 修改为 $x$。

输出格式

对于每个 1 l r 操作，输出一行两个整数，分别表示区间平均值和区间方差在模 $998244353$ 意义下的结果。两个结果均按照上述有理数取模规则输出。

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

提示

【样例说明】

第一次查询区间 $[1, 3]$，数据为 $1, 3, 2$，平均值为 $2$，方差为

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

第二次查询区间 $[2, 4]$，数据为 $3, 2, 4$，平均值为 $3$，方差为 $2$。随后将 $a_3$ 修改为 $5$，序列变为 $1, 3, 5, 4$。

第三次查询区间 $[1, 3]$，平均值为 $3$，方差为 $8$。

第四次查询区间 $[2, 4]$，平均值为 $4$，方差为 $2$。

【评测用例规模与约定】

对于 $50\%$ 的数据，保证 $n, m \le 3000$。

另有 $20\%$ 的数据，不存在操作 2 k x。

对于所有数据，保证：

• $1 \le n, m \le 3 \times 10^5$；
• $0 \le a_i, x \le 998244353$；
• 对于所有查询操作，$1 \le l \le r \le n$；
• 对于所有修改操作，$1 \le k \le n$。