C1545 [Ynoi]2016-E

内存限制:128 MB 时间限制:2000 ms

题目描述

您正在打 galgame,突然断电了,于是您跑去物管处问,结果发现是由于一个光头踢了变压器一脚导致的,可能还要修很久,于是您决定想一个之前见过的数据结构题:

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

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

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

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

由于结果可能过大,请输出答案 $\bmod 19260817$ 的结果。

输入格式

第一行两个数 $n,m$,表示有 $n$ 个序列,$m$ 次修改

然后 $n$ 个数,第 $i$ 个数是 $len_i$,表示第 $i$ 个序列的长度

之后 $n$ 行,每行 $len_i$ 个数,表示第 $i$ 个序列

之后 $m$ 行,每行三个数 $x,y,z$ 表示将第 $x$ 个序列的第 $y$ 个元素改为 $z$

输出

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

样例

样例输入 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

样例输出 1

1158 1158 1168 1168 1158 1158

提示

$1 \le n,m \le 100000$,序列中的元素均为 $32$ 位整型数,$len_i$ 的和 $ \le 100000$