SP1966 SKIVALL - Ski Valley

The Society of Sport of New Hampshire has decided to build a new attraction in White Mountains. For the first time, the world will see a ski-valley, a ski path that goes downhill then uphill. They believe that skiers can gain enough speed from going down in the first part in order to climb up the second part. To maximize the joy of visitors, they want to find the longest such path. To simplify calculations, they approximate the mountain terrain with a matrix of square fields and obtain the height of each field from the New Hampshire Geographical Institute. A ski-valley is a sequence of neighboring fields, such that height of fields only decreases along the sequence until some point, and then it only increases until its end. No field appears more than once in a ski-valley. Two fields are neighbors if they share a common edge. The length of a ski-valley is the number of fields in its sequence. More technically, the terrain is an _M_ x _N_ matrix of fields, where _(i, j)_ denotes a field in the _i_th row and _j_th column, and _h(i, j)_ denotes its height. A ski-valley is a sequence _(x $ _{1} $ , y $ _{1} $ ), (x $ _{2} $ , y $ _{2} $ ), ..., (x $ _{l} $ , y $ _{l} $ )_, such that: 1. for any _i_ (_1_ ≤ _i_ ≤ _l-1_), either _x $ _{i} $ = x $ _{i+1} $_ and |_y $ _{i} $ - y $ _{i+1} $_ | = _1_, or _y $ _{i} $ = y $ _{i+1} $_ and |_x $ _{i} $ - x $ _{i+1} $_ | = _1_ (neighbors rule) 2. if _i_ ≠ _j_ (_1_ ≤ _i, j_ ≤ _l_), then either _x $ _{i} $_ ≠ _x $ _{j} $_ or _y $ _{i} $_ ≠ _y $ _{j} $_ (no repeating rule), and 3. There exists a _k_ (_1_ ≤ _k_ ≤ _l_), such that _h(x $ _{1} $ , y $ _{1} $ )_ > _h(x $ _{2} $ , y $ _{2} $ )_ > ... > _h(x\_ $ _{k-1} $ , y\_ $ _{k-1} $ )_ > _h(x $ _{k} $ , y $ _{k} $ )_ < _h(x\_ $ _{k+1} $ , y\_ $ _{k+1} $ )_ < ... < _h(x $ _{l} $ , y $ _{l} $ )_ (down-up rule). The length of such ski-valley is _l_. They hire you, a reputable programmer, to write a program that will find a ski-valley of maximum length. If there are multiple ski-valleys with the same (maximum) length, you can choose any of them. Note: Yes, they were not cautious and also allowed a ski-valley to bo only downhill or only uphill, but your job is only to adhere to the specification they gave you!

The first line of the input contains _M_ and _N_ (1 ≤ M, N ≤ 60), respectively, separated by a space character. Each of the next _M_ lines contain _N_ numbers, such that the _j_th number in the _i_th line represents _h(i, j)_ (-10 $ ^{6} $ ≤ h(i, j) ≤ 10 $ ^{6} $ ). No two fields in the terrain are of the same height. Numbers on a line are separated by a space character.

In the first line of the output, write a single number _l $ _{max} $_ , which is the maximum length of a ski-valley. In the next _l $ _{max} $_ lines write a description of any ski-valley of that length. In each of the lines, write two integers separated by a space character, such that numbers _x $ _{i} $_ and _y $ _{i} $_ in the _i_th line represent _(x $ _{i} $ , y $ _{i} $ )_, the _i_th field in the ski-valley.