T501912 [CZSC 2024] 序列

# 本次比赛题目不一定按难度排序，请选手注意 # 请反复确认代码问题不大后再提交，否则会影响你的赋分分数

Caiwen 有一个长度为 $n$ 的序列。序列的第 $i$ 个位置有一个权重 $k_i$。在初始时，序列中第 $i$ 个数为 $a_i$。 对于一个序列，它的总价值定义为： $$\sum^{n}_{i=1} a_i^{k_i}$$ Caiwen 现在有 $m$ 个操作，每个操作给出两个数 $x$ 和 $y$，意思是将序列中第 $x$ 个数字修改为 $y$。Caiwen 想知道在每次操作之后新序列的价值为多少。

第一行，输入两个正整数 $n$ 和 $m$。 第二行输入 $n$ 个正整数，第 $i$ 个正整数表示 $k_i$。 第三行输入 $n$ 个正整数，第 $i$ 个正整数表示 $a_i$。 接下来输入 $m$ 行，每行包含两个正整数 $x$ 和 $y$。

输出 $m+1$ 行。 第一行先输出序列最开始时的总价值。 接下来 $m$ 行，第 $i$ 行输出第 $i$ 次操作后新序列的总价值。 **由于序列的总价值可能很大，所以你在每次输出序列总价值时只需要输出总价值对 $19260817$ 取模后的结果即可。**

**【样例 1 解释】** 初始时序列为 `1 1 4 5 1 4`，总价值为 $1^1+1^2+4^1+5^2+1^1+4^2=49$。 第一次操作后序列变成了 `1 3 4 5 1 4`，总价值为 $1^1+3^2+4^1+5^2+1^1+4^2=56$。 第二次操作后序列变成了 `1 3 4 1 1 4`，总价值为 $1^1+3^2+4^1+1^2+1^1+4^2=32$。 第二次操作后序列变成了 `1 3 4 1 1 2`，总价值为 $1^1+3^2+4^1+1^2+1^1+2^2=20$。 **【数据范围】** 对于所有数据，都有 $1\le n \le 3\times 10^4$，$0\le m \le 3\times 10^4$，$1\le k \le 10^3$，$1\le a_i,y \le 10^9$，$1\le x\le n$。 |测试点编号|$m$|$n$|$k$|特殊性质| |-|-|-|-|-| |$1\sim3$|$\le 100$|$\le 100$|$\le 100$|存在| |$4\sim5$|$\le 100$|$\le 100$|$\le 100$|无| |$6$|$\le 100$|$\le 100$|$=1$|存在| |$7\sim8$|$\le 100$|$\le 100$|$=1$|无| |$9\sim10$|$\le 3\times 10^4$|$\le 3\times 10^4$|$=1$|无| |$11$|$\le 100$|$\le 100$|$\le 3$|存在| |$12\sim13$|$\le 100$|$\le 100$|$\le 3$|无| |$14\sim15$|$\le 3\times 10^4$|$\le 3\times 10^4$|$\le 3$|无| |$16\sim17$|$=0$|$\le 10^4$|$\le 10^3$|无| |$18\sim20$|$=0$|$\le 3\times 10^4$|$\le 10^3$|无| |$21\sim22$|$\le 10^4$|$\le 10^4$|$\le 10^3$|无| |$23\sim25$|$\le 3\times 10^4$|$\le 3\times 10^4$|$\le 10^3$|无| 特殊性质：保证序列中每个数时时刻刻都不超过 $10$。