#B3909. 颜料覆盖

颜料覆盖

题目背景

一副精美的画作可能需要很多次重复的颜料涂抹。涂抹的一层层颜料会产生许多覆盖。这一次我们将这一个情景简化后交给了你,希望你能够解开颜料覆盖的奥秘。

题目描述

给定一个 nnmm 列的矩阵 aa。每一行代表画作的一块区域。每一行从前往后分别代表 mm 次绘画。

ai,ja _ {i, j} 代表序列中第 ii 行第 jj 列的元素,ai,ja _ {i, j} 代表区域 ii 在第 jj 次绘画中被涂抹的颜料强度。如果 ai,j=0a _ {i, j} = 0,那么代表区域 ii 在第 jj 次中未被涂抹。

现在,对于每个区域,你需要找出涂抹强度最大的一次是哪一次。同时,你需要找出,在这一次之前,有多少次涂抹(不计算未涂抹的情况)强度比这一次小。

保证对于某个区域,不会出现两次涂抹强度相同且最大。

输入格式

输入共 n+1n + 1 行。

第一行为两个整数 n,mn, m,分别代表区域数和绘画次数。
接下来 nn 行,每行 mm 个整数,代表矩阵 aa

输出格式

输出共 nn 行,每行两个整数,分别代表涂抹强度最大的一次是哪一次,和在这一次之前,有多少次涂抹(不计算未涂抹的情况)强度比这一次小。

3 5
0 1 0 3 2
0 0 1 0 0
1 1 3 4 5
4 1
3 0
5 4

提示

样例 1 解释

  • 第一行(第一个区域)中,第 4\color{red}4 次涂抹的强度最大,为 33。在第 44 次之前,有且仅有第 22 次这一次「有涂抹(不为 00)」且「强度比第 44 次小」,故答案为 4 1
  • 第二行(第二个区域)中,第 3\color{red}3 次涂抹的强度最大,为 11。在第 33 次之前,该区域没有被涂抹过(即第 33 次之前全为 00),故答案为 3 0
  • 第三行(第三个区域)中,第 5\color{red}5 次涂抹的强度最大,为 55。在第 55 次之前,有 4\color{red}4 次「有涂抹」且「强度比第 55 次小」,因此答案为 5 4

数据规模与约定

对于 100%100\% 的数据,保证 1n,m1061 \leq n, m \leq 10 ^ 61n×m1061 \leq n \times m \leq 10 ^ 60ai,j1090 \leq a _ {i, j} \leq 10 ^ 9

测试点 nn mm 特殊性质
11 =1= 1
232 \sim 3 10\leq 10
464 \sim 6 103\leq 10 ^ 3
77 1\leq 1 106\leq 10 ^ 6
88 106\leq 10 ^ 6 1\leq 1
9109 \sim 10 106\leq 10 ^ 6 每一行的第一个元素是这一行的最大值
111211 \sim 12 每一行的最后一个元素是这一行的最大值
131413 \sim 14 每一行有且仅有一个非 00 元素
152015 \sim 20

保证在矩阵的某一行中不存在两个元素相同且最大,保证不存在某一行全部为 00