The weight of a sequence is defined as the number of distinct elements in it. For example, the weight of $[1, 2, 3, 3]$ is $3$.

Given $n$ sequences, we choose one non-empty contiguous substring from each sequence and concatenate them. Calculate the sum of the weights of all sequences formed by all possible choices.

If a sequence can be formed in multiple ways, it is counted multiple times.

This problem includes modification operations; please refer to the input format for details.

Since the result may be very large, output the answer modulo $19260817$.

Input

The first line contains two integers $n$ and $m$, representing $n$ sequences and $m$ modifications.

The second line contains $n$ integers, where the $i$-th integer is $len_i$, the length of the $i$-th sequence.

The next $n$ lines each contain $len_i$ integers, representing the $i$-th sequence.

The following $m$ lines each contain three integers $x, y, z$, indicating that the $y$-th element of the $x$-th sequence is changed to $z$.

Output

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

Examples

Input 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

Output 1

1158
1158
1168
1168
1158
1158

Subtasks

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

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

There are 50 test cases in total.