Гном Торин нашел план покинутой пещеры, в которой жил горный король Норус. На плане обозначено место, где находится огромный клад. Горный король защитил свое богатство от искателей кладов, для чего расположил в пещере \textbf{L} каменных блоков, которые двигаются и могут раздавить искателя, и которые останавливаются, когда сокровища найдены. План задан в виде прямоугольной целочисленной матрицы \textbf{M}×\textbf{N}, элементами которой могут быть: \textbf{-2} (клад), \textbf{-1 }(стена), \textbf{0} (пустое место), положительное число \textbf{K} (элемент \textbf{K}--го блока). \textbf{K}--й блок состоит из всех элементов, обозначенных числом \textbf{K}. Блок не обязательно связный, но все его элементы движутся синхронно. Нули в крайних строках или столбцах матрицы обозначают входы в пещеру. Отдельно указано начальное направление движения каждого блока (\textbf{1} -- вверх, \textbf{2} -- направо, \textbf{3} -- вниз, \textbf{4} -- влево). Гном занимает клетку-вход. После этого он движется по таким правилам: на протяжении каждой секунды первым перемещается гном на пустую клетку из 4-х соседних (вверх, вниз, влево или направо) или остается на месте. Потом, на протяжении той же секунды, перемещается каждый блок на одну клетку (вверх, вниз, влево или направо): сначала первый, за ним второй и т.д. Если перед каким-нибудь элементом в направлении его движения находится стена, край пещеры, клад или другой блок, то на этом ходе блок не движется, а направление его движения изменяется на противоположное. Если блок во время движения попал в клетку с гномом, то гном гибнет. Написать программу CAVE для поиска безопасного пути, который приведет к кладу за наименьшее время, считая, что такой путь существует. \InputFile Входной файл в первой строке содержит три числа \textbf{M}, \textbf{N} и \textbf{L }--- количество блоков (\textbf{3} ≤ \textbf{M} ≤ \textbf{75}, \textbf{3} ≤ \textbf{N} ≤ \textbf{75}, \textbf{0} ≤ \textbf{L} ≤ \textbf{1000}). В следующих \textbf{M} строках содержаться \textbf{N} целых чисел --- план пещеры. В следующих \textbf{L} строках заданы начальные направления их движения в порядке увеличения номеров. \OutputFile Выходной файл в первой строке должен содержать число \textbf{K} --- время прохождения пути в секундах. В следующих \textbf{K+1} строках --- координаты положения гнома в каждую секунду (начиная с координат входа). Координаты должны быть заданы в порядке "строка столбец". Если существует несколько путей, достаточно указать один из них.