山海之侧,水天之间
题号:NC203031
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

    在神话世界中,有这样一块悬浮在虚空中的孤独岛屿,整个岛屿呈长方形,由若干条经纬线划分为网格,每个格子都是高度不同的平台,这些平台上有动物在繁衍生息,因为神话世界的物理定律和现实世界不同,动物可以随意地在两个相邻的平台之间跳跃行动。岛屿的最外围是极高的屏障,阻碍了一切物体的进出。

    因为屏障的存在,从天而降的雨水会在这个岛屿上不断蓄积,岛屿上的动物是无法涉水的,因此,如果两块陆地被水域所隔离,那么这两块陆地上的动物便会产生生殖隔离,从而向两个不同方向进化成为截然不同的物种。被水域淹没的平台上面的生物会全部死亡,因此,如果最高的平台也被淹没,这个岛屿便成为了没有生命的世界。

    为了方便讨论,我们假设时间节点是离散的,每个时间节点,岛屿上的水位升高个单位,然后如果某两块陆地被隔开,那么这两块陆地上的生物立刻演化为两种不同物种。

    现在,给出你这个岛屿的地貌,记这个岛屿完全没有水的时间为时刻,那么时刻,所有高度小于的平台将被淹没。

    请你从时刻开始,给出所有物种数量发生变化的时间节点(包括时间点),并给出这些时间上物种的数量,直到物种消亡殆尽。

输入描述:

第一行输入,代表岛屿的大小是

从第二行开始输入个整数组成的矩阵,代表每一个网格平台的高度。

输出描述:

每当物种数量发生变化时,输出一行共两个数字,第一个是当前时间节点,第二个是当前物种数量。
示例1

输入

复制
5 5
4 4 5 4 4
4 1 2 1 4
3 2 3 2 3
4 1 2 1 4
4 4 6 4 4

输出

复制
1 1
3 2
6 1
7 0

说明

o代表被水淹没,*代表未被水淹没
1时刻
*****
*****
*****
*****
*****

2时刻
*****
*o*o*
*****
*o*o*
*****

3时刻
*****
*ooo*
*o*o*
*ooo*
*****

4时刻
*****
*ooo*
ooooo
*ooo*
*****

5时刻
oo*oo
ooooo
ooooo
ooooo
oo*oo

6时刻
ooooo
ooooo
ooooo
ooooo
oo*oo

7时刻
ooooo
ooooo
ooooo
ooooo
ooooo
示例2

输入

复制
2 2
2 3
3 2

输出

复制
1 1
3 2
4 0

备注:

保证

平台高度在范围内