You have a *n* × *n* board,
where each position is permitted or prohibited.
Given the initial position of a knight,
you must determine if it is possible
that the knight passes exactly once in each permitted position,
doing the jumps of chess
(that is, increasing or decreasing one of the dimensions in a unit,
and the other dimension in two units).

**Input**

Input consists of a natural 3 ≤ *n* < 10,
followed by *n* lines with *n* characters each one:
a `’*’` indicates a prohibited position,
a dot indicates a permitted position.
Finally, a pair of integer numbers *r* and *c* between 1 and *n*
indicates the initial row and column of the knight;
the corner on the top and on the left is (1, 1).
The initial position of the knight will never be prohibited.

**Output**

Your program must print a path of the knight for all the permitted position
following the format of the instances.
Notice that each position for which the knight passes
is marked with two digits (being the first digit a 0 if it is needed),
starting in *01* and increasing.

If there are more than a possible path, choose one of them.
If the is not any possible solution,
your program must print `"no sol"`.

Public test cases

**Input**

4 .... .... .... ...* 4 1

**Output**

10 15 06 03 07 04 09 12 14 11 02 05 01 08 13 **

**Input**

5 ...*. .*... ....* .*... *..*. 3 2

**Output**

02 13 18 ** 04 19 ** 03 08 17 14 01 12 05 ** 11 ** 07 16 09 ** 15 10 ** 06

**Input**

3 ... ... ... 1 1

**Output**

no sol

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++