Problem Description

The time limit was changed to 1 s after the contest.

ZHY once again misread the problem during the contest.

For two sets $A,B$ each of size $x$, satisfying $A\cap B=\varnothing$ (the empty set), ZHY defines $f(A,B)$ as follows:

• Let $C=A\cup B$. Sort the elements in $C$ in increasing order.

• $f(A,B)=\displaystyle \sum_{i=1}^x C_i$.

Now, ZHY has $n$ sets $S_1,S_2,\cdots,S_n$, each of size $m$. He wants to know the value of $\displaystyle \sum_{i=1}^n\sum_{j=i + 1}^n f(S_i,S_j)$.

However, ZHY is not satisfied with this. So he performs $q$ modification operations. In each operation, one set is given again. After each modification, output the answer once, i.e., $\displaystyle \sum_{i=1}^n\sum_{j=i + 1}^n f(S_i,S_j)$. It is guaranteed that at any time, all elements within any set are pairwise distinct, and the intersection of any two sets is empty.

Input Format

The first line contains three integers $n,m,q$.

Lines $2$ to $n+1$ each contain $m$ integers describing the sets $S_1,S_2,\cdots,S_n$. The $m$ numbers on line $i+1$ are the $m$ integers in set $S_i$.

Then follow $q$ lines. In each line, the first integer is $x$, indicating the index of the set to be modified. The following $m$ numbers are the $m$ integers in the new $S_x$.

Output Format

The first line contains one integer, the initial answer.

Then output $q$ lines, each containing one integer, the answer after each modification.

3 2 2
1 3
2 6
4 8
1 3 5
2 7 9

13
18
26

Hint

This problem uses bundled testdata.

For all data, $0 \le n, q \le 10^4$, $1 \le m \le 100$, $1 \le S_{i,j} \le 10^9$. It is guaranteed that at any time, for $\forall i\in [1,n],\kern{2pt}j \in [1,m],\kern{2pt}i' \in[1,n],\kern{2pt}j'\in [1,m]$, if $i \ne i'$ or $j \ne j'$, then $S_{i,j} \ne S_{i',j'}。$

Translated by ChatGPT 5