#518. 「LibreOJ β Round #2」数论只会 GCD

内存限制:512 MiB 时间限制:2333 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: nzhtl1477

题目描述

定义一个序列的权值为不同数字的个数。例如 [1,2,3,3] 的权值为 3

现在有 n 个序列,我们在每个序列里面选一个连续非空子串,拼接起来,求所有选法得到的序列的权值之和。

如果一个序列能通过多种方法被选择出来,那么计算多次。

本题带修改操作,格式请参考输入格式。

由于结果可能过大,请输出答案 \mathop{\text{mod}}{19260817} 的结果。

输入格式

第一行两个数 n,m ,表示有 n 个序列, m 次修改。
然后 n 个数,第 i 个数是 \text{len}_i ,表示第 i 个序列的长度。
之后 n 行,每行 \text{len}_i 个数,表示第 i 个序列。
之后 m 行,每行三个数 x,y,z 表示将第 x 个序列的第 y 个元素改为 z

输出格式

输出 m + 1 行,依次表示初始局面以及每次修改后的答案。

样例

样例输入

2 5
6 6
1 3 1 1 3 2 
2 3 3 2 1 1 
1 1 1
1 1 2
1 1 2
1 1 1
1 1 1

样例输出

1158
1158
1168
1168
1158
1158

数据范围与提示

1\leq n,m\le 100000 ,序列中的元素均为 32 位整型数, \sum \text{len}_i \le 100000