Ліс

У середній смузі Рудоляндії іноді росте ліс. Щоб відокремити ліс від корисних орних земель, між лісом і полем було збудовано паркан. Проте ліс із часом розростається, і паркан потребує перенесення.

Місцевість можна подати як карту N \times M клітинок. Кожна клітинка містить або ліс, або поле, або паркан. Клітинки, які містять паркан, мають такі властивості:

1. Паркан зв'язний. Це означає, що з кожної клітинки паркану можна дійти до будь-якої іншої, пересуваючись лише по сусідніх клітинках (сусідніми вважаються клітинки, які мають спільну сторону).

2. Паркан мінімальний за включенням, тобто якщо прибрати якусь клітинку з паркану (замінивши її на ліс або поле), він перестане бути парканом.

3. Паркан розділяє ліс і поле: всі клітинки ліворуч від паркану — це ліс, а всі клітинки праворуч від паркану — поле.

4. Паркан можна подати у вигляді послідовності клітинок так, що кожна наступна клітинка перебуває ліворуч, праворуч або нижче попередньої.

Вам дозволяється використовувати для паркану всі клітинки, які він займав спочатку, а також клітинки, що знаходяться не більше ніж на одну праворуч від початкових клітинок паркану (використовувати лівий і правий стовпці карти заборонено). Потрібно побудувати паркан мінімальної довжини, який задовольняє всім зазначеним вимогам. Відомо, що початковий паркан дійсний, а також, що лівий стовпець карти повністю зайнятий лісом, а правий стовпець — полем.