Печера
Гном Торин знайшов план кинутої печери, у якій жив горний король Норус. На плані позначено місце, де знаходиться величезний скарб. Горний король захистив своє богатство від шукачів скарбів, для чого розмістив у печері L кам'яних блоків, які рухаються і можуть роздавити шукача, і які зупиняються, коли скарб знайдено.
План подано у вигляді прямокутної цілочисельної матриці M×N, елементами якої можуть бути: -2 (клад), -1 (стіна), 0 (порожнє місце), додатнє число K (елемент K–го блоку). K–й блок складається з усіх елементів, позначених числом K. Блок не обов'язково зв'язний, але усі його елементи рухаються синхронно. Нулі у крайніх рядках чи стовбцях матриці позначають входи до печери. Окремо вказано початковий напрямок руху кожного блоку (1 – вгору, 2 – праворуч, 3 – вниз, 4 – ліворуч).
Гном займає клітинку-вхід. Після цього він рухається за такими правилами: на протязі кожної секунди першим переміщується гном на порожню клітинку з 4-х сусідніх (вгору, вниз, ліворуч чи праворуч) або залишається на місці. Потім, на протязі тієї ж секунди, переміщується кожен блок на одну клітинку (вгору, вниз, ліворуч чи праворуч): спочатку перший, за ним другий і т.д. Якщо перед яким-небудь елементом у напрямку його руху знаходиться стіна, край печери, клад чи інший блок, то на цьому ході блок не рухається, а напрямок його руху змінюєеться на протилежний. Якщо блок під час руху потрапив у клітинку з гномом, то гном гине.
Напишіть програму CAVE для пошуку безпечного шляху, який приведе до кладу за найменший час, вважаючи, що такий шлях існує.
Вхідні дані
Вхідний файл у першому рядку містить три числа M, N та L — кількість блоків (3 ≤ M ≤ 75, 3 ≤ N ≤ 75, 0 ≤ L ≤ 1000). У наступних M рядках міститься N цілих чисел — план печери. У наступних L рядках задано початкові напрямки їх руху у порядку збільшення номерів.
Вихідні дані
Вихідний файл у першому рядку повинен містити число K — час проходження шляху в секундах. У наступних K+1 рядках — координати положення гнома кожної секунди (починаючи з координат входу). Координати повинні бути задані у порядку "рядок стовбчик". Якщо існує декілька шляхів, достатньо вказати один з них.