[HNOI2019]序列

题号：NC50731
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给定一个长度为n的序列 $A_1, \ldots,A_n$ ，以及m个操作，每个操作将一个 $A_i$ 修改为k。第一次修改之前及每次修改之后，都要求你找到一个同样长度为n的单调不降序列 $B_1, \ldots,B_n$ ，使得 $\sum_{i=1}^n(A_i−B_i)^2$ 最小，并输出该最小值。需要注意的是每次操作的影响都是独立的，也即每次操作只会对当前询问造成影响。为了避免精度问题，我们保证这个最小值是个分数，也即能表示为两个非负整数相除的形式：x/y。那么你将要输出 $(x \times y^{P-2}) \bmod P$ 的值，表示模意义下x/y的值。其中P=998244353是一个大质数。

输入描述:

第一行两个非负整数n,m，代表序列长度和操作数。
第二行有n个由空格隔开的正整数，代表序列。
接下来m行每行两个正整数i,k，代表将修改为k。

输出描述:

输出m+1行每行一个整数，第i行输出第i−1次修改后的答案。特别的，第1行应为初始局面的答案。

示例1

输入

复制

输出

复制

说明

第一个询问的最优B序列为：{5,5,5,5,5 }。
第二个询问的最优B序列为：{1,2,4,5,5 }。
第三个询问的最优B序列为：{3,3,4,5,5 }。
第四个询问的最优B序列为：{5,5,5,6,6 }。
样例是存在最优方案使皆为整数的特殊情况。

备注:

对于前的数据，保证，，且存在一种最优方案，使得皆为整数。
对于前的数据，保证。
对于另外的数据，保证m=0。
对于另外的数据，保证。
对于所有数据，保证。