Description

You are playing a galgame when the power suddenly goes out. You run to the property management office to ask, and find out it was because a bald guy kicked the transformer, and it may take a long time to fix. So you decide to think about a data structure problem you saw before:

Define the weight of a sequence as the number of distinct numbers in it. For example, $[1,2,3,3]$ has weight $3$.

Now there are $n$ sequences. For each sequence, we choose a non-empty contiguous substring, and concatenate them. Compute the sum of the weights of the resulting sequence over all choices.

If a sequence can be obtained in multiple ways, count it multiple times.

This problem includes modification operations; see the input format.

Since the result may be too large, output the answer $\bmod 19260817$.

Input Format

The first line contains two integers $n,m$, meaning there are $n$ sequences and $m$ modifications.

The second line contains $n$ integers; the $i$-th number is $len_i$, meaning the length of the $i$-th sequence.

Then follow $n$ lines; the $i$-th line contains $len_i$ integers, representing the $i$-th sequence.

Then follow $m$ lines; each line contains three integers $x,y,z$, meaning change the $y$-th element of the $x$-th sequence to $z$.

Output Format

Output $m + 1$ lines, each containing one integer, representing the answer for the initial state and after each modification, in order.

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

Hint

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477 ( partially uploaded )

$1 \leq n,m,len_i \leq 10^5$. The elements in the sequences are all $32$-bit integers, and $\sum len_i \leq 10^5$.

There are $50$ test cases.

Translated by ChatGPT 5