409384: GYM103495 J Anti-merge

In Kanade's daily work, there are a lot of documents for her to process. One of Kanade's jobs is to process tables, like this:

Kanade doesn't like repetitive numbers. So she installs a plugin to merge adjacent cells with the same content. The plugin will first merge cells with the same content in every column and then merge cells with the same content (and height, if ones are merged in the first step) in every row. For example, the table above will look like this with the plugin:

This plugin works well for Kanade, but it also poses some problems. For instance, some projects require her not to merge the cells. To meet this, Kanade can add tags to some cells. A tag is part of the content of a cell, but it is not displayed. So if two cells display the same number but have different tags, they will not be merged. But if they have the same tags, they will still be merged.

Now Kanade needs to process a table with $$$n$$$ rows and $$$m$$$ columns which requires her not to merge the cells. To keep any cells from being merged, Kanade would like to know how many kinds of tags at least need to be added. She also wants to know how to add tags to minimize the number of tags when the number of kinds of tags is the least.

The first line of input contains two integers $$$n,m$$$ ($$$1\le n,m\le 500$$$), indicating the number of rows and columns of the table.

For the next $$$n$$$ lines, each line contains $$$m$$$ integers in the range of $$$[1,10^9]$$$, indicating the content of the table.

The first line of the output contains two integers. The first integer $$$t$$$ ($$$0\le t \le n\times m$$$) indicates the minimum number of kinds of tags that need to be added. The second integer $$$k$$$ ($$$0\le k \le n\times m$$$) indicates the minimum number of tags that need to be added when the number of kinds of tags is the least.

For the next $$$k$$$ lines, each line contains three integers $$$x,y,c$$$ ($$$1 \le x \le n$$$, $$$1 \le y \le m$$$, $$$1\le c\le t$$$), indicating that tag $$$c$$$ is added to the cell in the $$$x$$$-th row and $$$y$$$-th column. If there are multiple solutions, output any.

1 3
1 1 4

1 1
1 1 1

1 3
5 1 4

0 0

2 3
1 1 4
5 1 4

1 2
1 2 1
2 3 1

Please note that if the length or format of your output does not match the answer, you will possibly get a Presentation Error verdict.