Sum of the m Smallest Elements over Disjoint Set Pairs

You are given n sets \(S_1, S_2, \dots, S_n\), each containing exactly m distinct integers. It is guaranteed that for any two different sets \(S_i\) and \(S_j\), we have \(S_i \cap S_j = \varnothing\).

For any two sets \(A\) and \(B\) (each of size \(m\)) with \(A\cap B=\varnothing\), define the function \[ f(A,B)=\sum_{i=1}^{m} C_i, \] where \(C = A\cup B\) and \(C_1, C_2, \dots, C_{2m}\) denotes the elements of \(C\) sorted in increasing order. In other words, \(f(A,B)\) is the sum of the m smallest elements in \(A\cup B\).

Your task is to compute the quantity \[ \sum_{1\le i<j\le n} f(S_i,S_j), \] that is, the sum of \(f(S_i,S_j)\) over all pairs \((i,j)\) such that \(1 \le i < j \le n\).

After the initial configuration of the sets is given, there will be q modification operations. In each operation, a new set is provided to replace one of the existing sets. After each modification, you must output the updated value of \[ \sum_{1\le i<j\le n} f(S_i,S_j). \]

It is guaranteed that during and after every modification, every set contains m distinct integers and any two sets remain disjoint.

inputFormat

The first line contains three integers n, m, and q --- the number of sets, the size of each set, and the number of modification operations.

The next n lines each contain m integers, representing the initial elements of set \(S_i\) (\(1 \le i \le n\)).

Then, there are q modification operations. Each operation is given on a separate line. Each such line begins with an integer k (1-based index) indicating which set to update, followed by m integers representing the new elements for set \(S_k\).

outputFormat

For each modification operation, output a single line containing the updated value of \(\sum_{1\le i<j\le n} f(S_i,S_j)\).

sample

2 2 1
1 3
2 4
1 0 5

2