Шелдон и Леонард в очередной раз решили написать программу для игры в 3D-шахматы. Пока они сконцентрировали внимание на реализации стратегии самой игры. Но чтобы не терять время, они бросили клич к научной общественности — помочь реализовать простейшие подпрограммы, на которые им, естественно, жаль тратить свое драгоценное время.
Одна из задач — определить путь, посредством которого конь может попасть из одной клетки в другую за наименьшее число ходов, всё время оставаясь на одном и том же уровне (каждый уровень является плоской квадратной шахматной доской). В пределах одного уровня конь перемещается по стандартным шахматным правилам, но некоторые клетки доски перемещают оказавшиеся на них фигуры на другие уровни, поэтому коню запрещено оказываться в таких клетках в конце хода.
Первая строка содержит целое число N (3 ≤ N ≤ 1000) — размер шахматной доски.
Следующие N строк описывают шахматную доску. i-я из них содержит N символов, j-й из которых равен '.', если клетка (i; j) является обычной клеткой доски, '*', если клетка является началом или концом искомого пути, либо '+', если в клетку запрещено попадать коню.
Гарантируется, что ввод содержит ровно два символа '*'.
В первой строке выведите число M — количество клеток, входящих в искомый путь, включая начальные и конечные клетки.
Далее выведите M строк, каждая из которых содержит пару целых чисел — вертикальную и горизонтальную координаты клеток, которые посещает конь; строки должны быть упорядочены в порядке обхода. Строки доски нумеруются сверху вниз, начиная с 0. Столбцы доски нумеруются слева направо, начиная с 0.
Если искомого пути не существует, выведите единственное число 0.
5
.....
.**..
.....
.....
.....
4
1 1
2 3
0 4
1 2
5
*..*.
..++.
.....
.....
.....
6
0 0
2 1
4 0
3 2
2 4
0 3
5
*....
..+..
.+...
.....
....*
0
Шахматный конь может перемещаться на две клетки вверх, влево, вниз или вправо, а затем на одну клетку в любом перпендикулярном направлении. Конь «перепрыгивает» через клетки, то есть непосредственно посещает только начальную и конечную клетки хода.
