spider

Omul păianjen (Spiderman) sare de pe o clădire pe alta, aflată în imediata vecinătate, în nord, est, sud sau vest.

Figura 1 din enunțul original al problemei spider.Mărește schema ↗

Clădirile din cartierul omului păianjen au o înălțime exprimată în numere naturale și sunt așezate pe $m$ rânduri, câte $n$ pe fiecare rând. Spiderman va alege să sară pe una dintre clădirile vecine, care are înălțimea mai mică sau egală, iar diferența de înălțime este minimă. Dacă există mai multe clădiri vecine de aceeași înălțime, omul păianjen aplică ordinea preferențială nord, est, sud, vest, dar nu sare încă o dată pe o clădire pe care a mai sărit. Scopul omului păianjen este acela de a reuși să facă un număr maxim de sărituri succesive.

Cerință

Scrieți un program care determină numărul maxim de sărituri succesive, pe care îl poate efectua, pornind de la oricare dintre clădiri, precum și pozițiile clădirilor care formează drumul maxim.

Date de intrare

Fișierul spider.in conține, pe prima linie, două numere naturale, $m$ și $n$, despărțite printr-un spațiu. Fiecare dintre următoarele $m$ rânduri conține $n$ numere naturale, separate prin câte un spațiu, reprezentând înălțimile clădirilor.

Date de ieșire

Fișierul de ieșire spider.out va conține, pe prima linie, un singur număr natural $k$, reprezentând numărul maxim de sărituri. Următoarele $k$ linii vor conține câte două numere naturale, separate printr-un spațiu, reprezentând coordonatele clădirilor care formează drumul maxim, în ordinea parcurgerii. Dacă există mai multe soluții, în fișierul de ieșire se va scrie drumul care pornește de la poziția ($i, j$) cu $i$ minim, iar dacă există mai multe soluții cu același $i$ minim, se va scrie în fișier soluția cu $i$ și $j$ de valoare minimă.

Restricții și precizări

• $1 \leq m, n \leq 1 \ 000$;
• Înălțimile clădirilor sunt numere naturale din intervalul $[1, 10 \ 000 \ 000]$.
• În orice zonă pătratică de $2 \times 2$ clădiri vecine există cel mult $2$ clădiri de aceeași înălțime.

Exemplu

spider.in

5 5
35 38 42 40 50
34 38 30 75 50
70 78 88 86 30
39 90 88 23 25
35 80 89 90 34

spider.out

8
5 4
5 3
4 3
3 3
3 4
2 4
2 5
1 5
1 4

Explicație

Spiderman pornește de pe blocul de $90$ de metri aflat în poziția $(5, 4)$, face $8$ sărituri și ajunge în poziția $(1, 4)$, de unde nu mai are posibilități de a sări.