在 Kanade 的日常工作中，她需要处理大量的文档。她的工作之一是处理如下所示的表格：

Kanade 不喜欢重复的数字。因此，她安装了一个插件来合并内容相同的相邻单元格。该插件会首先合并每一列中内容相同的单元格，然后合并每一行中内容相同（且在第一步中合并后高度相同）的单元格。例如，使用该插件后，上面的表格将显示为：

这个插件对 Kanade 来说很好用，但也带来了一些问题。例如，有些项目要求她不要合并单元格。为了满足这一点，Kanade 可以给一些单元格添加标签。标签是单元格内容的一部分，但它不会被显示出来。因此，如果两个单元格显示的数字相同但标签不同，它们就不会被合并。但如果它们有相同的标签，它们仍然会被合并。

现在 Kanade 需要处理一个 $n$ 行 $m$ 列的表格，要求她不能合并其中的任何单元格。为了防止任何单元格被合并，Kanade 想知道至少需要添加多少种标签。她还想知道在标签种类数最少的情况下，如何添加标签以使添加的标签总数最少。

输入格式

第一行包含两个整数 $n, m$ ($1 \le n, m \le 500$)，表示表格的行数和列数。

接下来的 $n$ 行，每行包含 $m$ 个范围在 $[1, 10^9]$ 内的整数，表示表格的内容。

输出格式

第一行包含两个整数。第一个整数 $t$ ($0 \le t \le n \times m$) 表示需要添加的最少标签种类数。第二个整数 $k$ ($0 \le k \le n \times m$) 表示在标签种类数最少的情况下，需要添加的最少标签总数。

接下来的 $k$ 行，每行包含三个整数 $x, y, c$ ($1 \le x \le n, 1 \le y \le m, 1 \le c \le t$)，表示将标签 $c$ 添加到第 $x$ 行第 $y$ 列的单元格中。如果存在多种方案，输出任意一种即可。

样例

输入 1

1 3
1 1 4

输出 1

1 1
1 1 1

输入 2

1 3
5 1 4

输出 2

0 0

输入 3

2 3
1 1 4
5 1 4

输出 3

1 2
1 2 1
2 3 1

说明

请注意，如果输出的长度或格式与答案不符，你可能会收到 Presentation Error 的判决。