Вася из задачи
A по-прежнему занят поиском кладов. Более того, у него появились последователи. Один из таких последователей попросил Васю помочь в своих поисках. Так, по карте сокровищ Васю просят восстановить кратчайший путь до клада. Конфигурация лабиринта совпадает с конфигурацией, описанной в задаче A (поле
\(N \times M (1 \le N, M \le 100, N \times M \le 100))\), в одной клетке которого находится клад, в K
клетках находятся входы в лабиринт).
Требуется вывести искомый путь.
Формат входных данных
Первая строка содержит 2 числа N<=100 и M<=100, задающие размеры лабиринта. Далее следует описание лабиринта: N
строк по M символов в каждой. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с сокровищем (такая клетка в лабиринте ровно одна).
В (N+2)-й строке находится число
\(K (1 \le K \le N \times M)\) - количество входов в лабиринт. Далее в K строках содержатся координаты входов. Так, в i-й строке содержатся числа
\(x_i\) и
\(y_i\), означающие, что i-й вход расположен в
\(x_i\)-й строке и в
\(y_i\)-м столбце
\((1 \le x_i \le N, 1\le y_i \le M)\). Гарантируется, что координаты входов попарно различны, и то, что все входы расположены в пустых клетках. Ни один из входов не находится в клетке с сокровищем.
Формат выходных данных
В первой строке вывести одно число - длину кратчайшего маршрута. В следующих строках необходимо вывести кратчайший маршрут. Каждую клетку маршрута (включая начальную и конечную) вывести на отдельной строке в формате
\(x_i\) \(y_i\), где
\(x_i\) - строка клетки, а
\(y_i\) - столбец клетки.
Если существует несколько путей минимальной длины, выведите любой. Если до сокровища невозможно добраться, в единственной строке выведите -1.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5 5
00000
00000
10*00
01111
00000
4
1 1
1 5
4 1
5 5 |
4
1 1
2 1
2 2
3 2
3 3 |
| 2 |
3 3
010
1*1
010
4
1 1
1 3
3 1
3 3
|
-1 |