B.数据结构(present)

题目描述

有一个 $n\times m$ 的矩阵 $C$ 。

你需要回答 $Q$ 组询问，每组询问会给出三个自然数 $x,y,k$，你需要回答：

如果将矩阵中除了第 $x$ 行的元素以及第 $y$ 列的元素以外，其他的元素全部置为 $0$，此时矩阵中所有元素的第 $k$ 大。

每次询问只是假设会对矩阵做修改的情况下进行的询问，实际上不会对矩阵做出任何修改。

输入格式

第一行三个自然数 $n,m,Q$ 。

接下来 $n$ 行，每行 $m$ 个自然数，表示矩阵 $C$ 。

接下来 $Q$ 行，每行三个自然数 $x,y,k$，表示一组询问。

输出格式

共 $Q$ 行，每行一个自然数，表示答案。

样例

输入样例

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

输出样例

3
7
8

数据范围

对于 $20\%$ 的数据，$n,m,Q\leq 100$ 。

对于 $50\%$ 的数据，$Q\leq 1000$ 。

对于额外 $20\%$ 的数据，$k=1$ 。

对于额外 $20\%$ 的数据，$n\leq 10$ 。

对于 $100\%$ 的数据，$n,m\leq 1000,Q\leq 10^5,1\leq k\leq n+m-1,1\leq C_{i,j}\leq n\times m$，$1\le x\le n$，$1\le y\le m$。保证 $C_{i,j}$ 两两不同。

时间限制 : 2000 ms

空间限制 : 512 MB