在神话世界中,有这样一块悬浮在虚空中的孤独岛屿,整个岛屿呈长方形,由若干条经纬线划分为网格,每个格子都是高度不同的平台,这些平台上有动物在繁衍生息,因为神话世界的物理定律和现实世界不同,动物可以随意地在两个相邻的平台之间跳跃行动。岛屿的最外围是极高的屏障,阻碍了一切物体的进出。
因为屏障的存在,从天而降的雨水会在这个岛屿上不断蓄积,岛屿上的动物是无法涉水的,因此,如果两块陆地被水域所隔离,那么这两块陆地上的动物便会产生生殖隔离,从而向两个不同方向进化成为截然不同的物种。被水域淹没的平台上面的生物会全部死亡,因此,如果最高的平台也被淹没,这个岛屿便成为了没有生命的世界。
为了方便讨论,我们假设时间节点是离散的,每个时间节点,岛屿上的水位升高个单位,然后如果某两块陆地被隔开,那么这两块陆地上的生物立刻演化为两种不同物种。
现在,给出你这个岛屿的地貌,记这个岛屿完全没有水的时间为时刻,那么
时刻,所有高度小于
的平台将被淹没。
请你从时刻开始,给出所有物种数量发生变化的时间节点(包括
时间点),并给出这些时间上物种的数量,直到物种消亡殆尽。
第一行输入
,代表岛屿的大小是
行
列
从第二行开始输入
个整数组成的矩阵,代表每一个网格平台的高度。
每当物种数量发生变化时,输出一行共两个数字,第一个是当前时间节点,第二个是当前物种数量。
保证
平台高度在
范围内