f * g
题号：NC279257
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定两个长度为 n 的序列 f,g。

定义 V=\sum_{i=1}^n\sum_{j=1}^nf_{\min(i,j)}\times g_{\max(i,j)}

同时有 Q 次操作：
  • 1,i,x：令 f_i=x
  • 2,i,x：令 g_i=x

注意每次修改不是独立的，本次修改会影响后续的询问。

jackle 想让你告诉他每次操作之后 V 的值是多少？

由于答案很大，请输出答案对 998244353 取模之后的结果。

输入描述:

第一行输入 2 个正整数 n,Q(1\leq n,Q\leq 1\times 10^5)，分别表示序列长度，操作次数。

第二行输入 n 个正整数 f_i(1\leq f_i\leq 10^9)。

第三行输入 n 个正整数 g_i(1\leq g_i\leq 10^9)。

接下来 Q 行，每行输入三个整数 t,i,x，其中 t\in \{1,2\}，1\leq i\leq n，1\leq x\leq 10^9。

输出描述:

输出 Q 行，每行一个整数，表示本次操作结束之后 V 的值是多少。（答案对 998244353 取模）
示例1

输入

复制 
4 3
1 2 3 4
4 3 2 1
1 2 1
2 3 4
1 4 9

输出

复制 
41
55
60
示例2

输入

复制 
3 2
1 1 1
2 2 2
1 1 3
2 2 9

输出

复制 
38
87