Шелдон и Леонард в очередной раз решили написать программу для игры в 3D-шахматы. Пока они сконцентрировали внимание на реализации стратегии самой игры. Но чтобы не терять время, они бросили клич к научной общественности — помочь реализовать простейшие подпрограммы, на которые им, естественно, жаль тратить свое драгоценное время.
Одна из задач — определить путь, посредством которого конь может попасть из одной клетки в другую за наименьшее число ходов, всё время оставаясь на одном и том же уровне (каждый уровень является плоской квадратной шахматной доской). В пределах одного уровня конь перемещается по стандартным шахматным правилам, но некоторые клетки доски перемещают оказавшиеся на них фигуры на другие уровни, поэтому коню запрещено оказываться в таких клетках в конце хода.
Первая строка содержит целое число N (3 ≤ N ≤ 1000) — размер шахматной доски.
Следующие N строк описывают шахматную доску. i-я из них содержит N символов, j-й из которых равен '.', если клетка (i; j) является обычной клеткой доски, '*', если клетка является началом или концом искомого пути, либо '+', если в клетку запрещено попадать коню.
Гарантируется, что ввод содержит ровно два символа '*'.
В первой строке выведите число M — количество клеток, входящих в искомый путь, включая начальные и конечные клетки.
Далее выведите M строк, каждая из которых содержит пару целых чисел — вертикальную и горизонтальную координаты клеток, которые посещает конь; строки должны быть упорядочены в порядке обхода. Строки доски нумеруются сверху вниз, начиная с 0. Столбцы доски нумеруются слева направо, начиная с 0.
Если искомого пути не существует, выведите единственное число 0.
Шахматный конь может перемещаться на две клетки вверх, влево, вниз или вправо, а затем на одну клетку в любом перпендикулярном направлении. Конь «перепрыгивает» через клетки, то есть непосредственно посещает только начальную и конечную клетки хода.
## Входные Данные
Первая строка содержит целое число N (3 ≤ N ≤ 1000) — размер шахматной доски.Следующие N строк описывают шахматную доску. i-я из них содержит N символов, j-й из которых равен '.', если клетка (i; j) является обычной клеткой доски, '*', если клетка является началом или концом искомого пути, либо '+', если в клетку запрещено попадать коню.Гарантируется, что ввод содержит ровно два символа '*'.
## Выходные Данные
В первой строке выведите число M — количество клеток, входящих в искомый путь, включая начальные и конечные клетки.Далее выведите M строк, каждая из которых содержит пару целых чисел — вертикальную и горизонтальную координаты клеток, которые посещает конь; строки должны быть упорядочены в порядке обхода. Строки доски нумеруются сверху вниз, начиная с 0. Столбцы доски нумеруются слева направо, начиная с 0.Если искомого пути не существует, выведите единственное число 0.
## Примеры
Входные данные5......**.................Выходные данные41 12 30 41 2Входные данные5*..*...++................Выходные данные60 02 14 03 22 40 3Входные данные5*......+...+............*Выходные данные0
## Примечание
Шахматный конь может перемещаться на две клетки вверх, влево, вниз или вправо, а затем на одну клетку в любом перпендикулярном направлении. Конь «перепрыгивает» через клетки, то есть непосредственно посещает только начальную и конечную клетки хода.
[samples]
**Definitions**
Let $ N \in \mathbb{Z} $ be the size of the square chessboard ($3 \leq N \leq 1000$).
Let $ B \in \{., *, +\}^{N \times N} $ be the board, where:
- $ B[i][j] = '.' $: normal cell,
- $ B[i][j] = '*' $: start or end cell (exactly two such cells),
- $ B[i][j] = '+' $: forbidden cell (constrained to avoid at the end of any move).
Let $ s = (r_s, c_s) $ and $ t = (r_t, c_t) $ be the coordinates of the two `*` cells (start and target).
Let $ \mathcal{M} = \{ (\pm 2, \pm 1), (\pm 1, \pm 2) \} $ be the set of 8 valid knight moves.
**Constraints**
1. The knight may only move to cells $ (i', j') $ such that:
- $ (i', j') \in [0, N-1] \times [0, N-1] $,
- $ B[i'][j'] \neq '+' $,
- $ (i', j') - (i, j) \in \mathcal{M} $.
2. The knight must not land on a `+` cell at the end of any move.
3. The path must start at $ s $ and end at $ t $.
**Objective**
Find the shortest path (minimum number of moves) from $ s $ to $ t $, visiting a sequence of valid cells.
Output:
- If a path exists:
- $ M $: number of cells in the path (including start and end),
- $ M $ lines: coordinates $ (r, c) $ of each visited cell in order.
- If no path exists: output `0`.