0200. Sieve Coding

Input file name: sieve.in
Output file name: sieve.out
Time limit: 250 ms
Memory limit: 32 megabytes

The coding process known as "Sieve" is made in the following way. The letters of the text are being written in cells of N*N matrix consequently from left to right, from top to bottom (the rest of the matrix is being filled with `*' symbol). The key of the code is a card (sieve) with the grid marked on it (the grid has the same size i. e. number of rows and columns as the matrix) which has some cells cut out from it. This card is laid upon the matrix and the letters are written out from the visible cells of the matrix in the order they appear. Then the sieve is turned 90 degrees clockwise and visible letters are written out again. Such an operation repeats 4 times. You should write a program that answers whether it is possible to encrypt a given string using a given sieve (it is considered that it can be done if each cell of the matrix occurs in encrypted string exactly once) and outputs the encrypted string.

Input file

There is a non-empty string S in the first line of the input file (it consists of the uppercase Latin letters and its length doesn't exceed 256). The second line contains integer number N (0<N<17). Next N lines contain N symbols each. These N lines represent the description of the sieve. Symbol `+' represents a hole in a corresponding cell of the grid and symbol `.' (dot) represents an opaque cell of the grid.

Output file

Write `No solution.' in the first line of the output file if the string can't be encrypted and write the result of encryption otherwise.

Examples:

sieve.insieve.out
ABCD 2 .+ ..BDCA


Source: Petrozavodsk Summer 2003. Saratov SU Contest, Wednesday, August 27

Discuss       Submit a solution



Printable version