Вершини
Альпініст, який мешкає на гірському острові, піднявся на одну з вершин і тепер прагне дістатися до вищої вершини.
Кожна точка на острові має позитивну висоту над рівнем моря (висота моря — 0). Якщо вершина, на якій зараз знаходиться альпініст, має висоту E_i, його мета — досягти вершини з висотою E_j (E_j > E_i). Оскільки він вже на вершині, немає прямого шляху вгору — щоб дістатися до вищої точки, альпіністу спочатку потрібно спуститися до нижчого рівня, а потім знову піднятися. Спуск не такий захоплюючий, як підйом, тому альпініст хоче максимізувати висоту найнижчої точки на шляху від поточного місця до вищої вершини.
Наприклад, якщо профіль острова зображено на малюнку, і альпініст знаходиться на вершині з висотою E_4, то є три вершини з вищою висотою (E_5, E_6 і E_7), але шлях з найнижчою точкою, що має найвищу висоту, веде до вершини з висотою E_7 — на цьому шляху він ніколи не опускається нижче рівня E_2 (в інших випадках він буде змушений спуститися до рівня E_1). Якщо він почав з E_5, відповідний найнижчий рівень буде E_3 (шлях до E_6), але якщо він почав з E_6, це буде E_1.
Карта острова — це двовимірна прямокутна таблиця розміром N×M, що описує висоту певних частин острова — число в клітинці вказує на висоту відповідного регіону. Дві клітинки є сусідніми, якщо вони мають спільну точку. Таким чином, кожна клітинка (крім тих, що на межі) є сусідньою з вісьмома іншими. Шлях — це послідовність клітинок, де кожні дві послідовні клітинки є сусідніми. Плоска область — це набір з однієї або більше клітинок з однаковою висотою, будь-яка пара яких з'єднана шляхом, що проходить лише через клітинки в межах набору. Будь-які дві сусідні клітинки з однаковою висотою належать до однієї плоскої області. Вершина — це плоска область, клітинки якої не мають сусідніх клітинок з вищою висотою.
Напишіть програму, яка знаходить усі вершини на острові і для кожної з них визначає висоту найвищої можливої найнижчої точки на шляху до якоїсь вершини з вищою висотою. Для найвищої вершини на острові (для якої немає вищої вершини на цьому острові) вважаємо, що альпініст залишить острів у пошуках вищих вершин, тому найнижча точка буде 0 (рівень моря).
Вхідні дані
Перший рядок вхідного файлу містить два додатні цілі числа N і M (1 ≤ N, M ≤ 2000, N×M ≤ 10^5), висоту і ширину карти відповідно. Наступні N рядків містять опис карти острова. Кожен з цих рядків містить M цілих чисел E_ij (1 ≤ E_ij ≤ 10^6), розділених пробілами. Висота клітинки E_ij (відповідної i-му рядку і j-му стовпцю на карті) задана як j-те число в i+1-му рядку файлу.
Вихідні дані
Перший рядок вихідного файлу повинен містити одне ціле число P, кількість знайдених вершин на острові. Наступні P рядків повинні містити по два цілі числа: висоту конкретної вершини і висоту найвищої можливої найнижчої точки на шляху до якоїсь вищої вершини. Інформація про вершини повинна бути записана в порядку спадання їх висоти; якщо кілька вершин мають однакову висоту, то вони повинні бути відсортовані в порядку спадання висоти найнижчої точки.
Коментар до прикладу 1:
Усі вершини позначені колами. Один з можливих шляхів від вершини з висотою 15 показаний темним кольором.