P14197 [ICPC 2024 Hangzhou R] Kind of Bingo

There is a grid with $n$ rows and $m$ columns. The cells in the grid are numbered from $1$ to $n \times m$, where the cell on the $i$-th row and the $j$-th column is numbered as $((i - 1) \times m + j)$. Given a permutation $p_1, p_2, \cdots, p_{n \times m}$ of $n \times m$, we're going to perform $n \times m$ operations according to the permutation. For the $i$-th operation, we'll mark cell $p_i$. If after the $b$-th operation, there is at least one row such that all the cells in that row are marked, and $b$ is as small as possible, then we say $b$ is the ``bingo integer`` of the permutation. You're given the chance to modify the permutation at most $k$ times (including zero times). Each time you can swap a pair of elements in the permutation. Calculate the smallest possible bingo integer after the modifications. Recall that a sequence $p_1, p_2, \cdots, p_{n \times m}$ of length $n \times m$ is a permutation of $n \times m$ if and only if each integer from $1$ to $n \times m$ (both inclusive) appears exactly once in the sequence.

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^4$) indicating the number of test cases. For each test case: The first line contains three integers $n$, $m$ and $k$ ($1 \le n, m \le 10^5$, $1 \le n \times m \le 10^5$, $0 \le k \le 10^9$), indicating the number of rows and columns of the grid and the number of modifications you can perform. The second line contains $n \times m$ distinct integers $p_1, p_2, \cdots, p_{n \times m}$ ($1 \le p_i \le n \times m$). It's guaranteed that the sum of $n \times m$ of all test cases will not exceed $10^5$.

For each test case output one line containing one integer indicating the smallest possible bingo integer after the modifications.

For the first sample test case, we can first swap $1$ and $15$, then swap $6$ and $12$ to get the sequence $[15, 4, 13, 12, 8, 11, 14, 2, 7, 10, 3, 1, 9, 5, 6]$. It's easy to see that after the $7$-th operation, all cells in the $3$-rd row will be marked. For the second sample test case, it's easy to see that after the $5$-th operation, all cells in the $2$-nd row will be marked. For the third sample test case, we don't need to make any modifications. It's easy to see that after the $3$-rd operation, all cells in the $1$-st row will be marked.