Description
A matrix can be regarded as ordered sequence of row vectors.
Let’s define the length of vector, and 2 kinds of operations for matrix.
- length of vector v: Euclidean norm, which means | v | = sqrt( ∑ (vi)2)
- switch (i, j): swap the i-th row with j-th row, which means ri ⟷ rj
- add (i,j): add j-th row to i-th row, which means ri ← ri + rj
Given one m x n matrix A, and K operations.
Your task is to find the longest row vector v in A after K operations.
If there’re more than one longest row vector, print the one with smaller row index.
Input
Three numbers m, n, K on the first line.
For each of following m lines, there’s a row vector ri of matrix A.
Every row vector consists of n numbers.
The next K lines contains one operation per line.
Each operation is one of “0 i j” or “1 i j”, denoting the operation switch (i,j) and add (i,j) respectively.
It’s guaranteed that:
- 1 ≤ m, n ≤ 1000
- 0 ≤ K ≤ 1000
- 0 ≤ i ≤ m and 0 ≤ j ≤ n
- -100 ≤ Each element in A ≤ 100
Output
Print the longest row vector after several operations in one line.
If there’re more than one longest row vector, print the one with smaller row index.
Note that there’s “\n” on the end of lines.
Explaination for Sample
