Flying Dream

Jerry, a middle school student, addicts himself to mathematical research. Maybe the problems he has thought are really too easy to an expert. But as an amateur, especially as a 15-year-old boy, he had done very well. He is so rolling in thinking the mathematical problem that he is easily to try to solve every problem he met in a mathematical way. One day, he found a piece of paper on the desk. His younger sister, Mary, a four-year-old girl, had drawn some lines. But those lines formed a special kind of concave polygon by accident as Fig. 1 shows.

Fig. 1 The lines his sister had drawn

"Great!" he thought, "The polygon seems so regular. I had just learned how to calculate the area of triangle, rectangle and circle. I'm sure I can find out how to calculate the area of this figure." And so he did. First of all, he marked the vertexes in the polygon with their coordinates as Fig. 2 shows. And then he found the result--0.75 effortless.

Fig.2 The polygon with the coordinates of vertexes

Of course, he was not satisfied with the solution of such an easy problem. "Mmm, if there's a random polygon on the paper, then how can I calculate the area?" he asked himself. Till then, he hadn't found out the general rules on calculating the area of a random polygon. He clearly knew that the answer to this question is out of his competence. So he asked you, an erudite expert, to offer him help. The kind behavior would be highly appreciated by him.

Input

The input data consists of several figures. The first line of the input for each figure contains a single integer n, the number of vertexes in the figure. (0 <= n <= 1000).

In the following n lines, each contain a pair of real numbers, which describes the coordinates of the vertexes, (xi, yi). The figure in each test case starts from the first vertex to the second one, then from the second to the third, …… and so on. At last, it closes from the nth vertex to the first one.

The input ends with an empty figure (n = 0). And this figure not be processed.

Output

As shown below, the output of each figure should contain the figure number and a colon followed by the area of the figure or the string "Impossible".

If the figure is a polygon, compute its area (accurate to two fractional digits). According to the input vertexes, if they cannot form a polygon (that is, one line intersects with another which shouldn't be adjoined with it, for example, in a figure with four lines, the first line intersects with the third one), just display "Impossible", indicating the figure can't be a polygon. If the amount of the vertexes is not enough to form a closed polygon, the output message should be "Impossible" either.

Print a blank line between each test cases.

Sample Input

5
0 0
0 1
0.5 0.5
1 1
1 0
4
0 0
0 1
1 0
1 1
0

In World War II, Germany once used an electronic encryption machine called Enigma, which played a decisive role in the initial victories of Nazi Germany. It was proved to be one of the most reliable encryption systems in history. However, it was the blind trust on the reliability of the machine that brought about the doom of its user.

The structure of a one-rotor Enigma is shown as follows (the Enigma has only six keys):

The key element of the Enigma is the rotor, as shown in the second figure, which uses electronic circuits to transform plaintext (input from keyboard) into cryptograph (output on screen). When one key on the keyboard is pressed, the corresponding cryptograph is shown on screen. Then the rotor will automatically revolve a one-letter-step to a different position. The following figures illustrate how the rotor works when letter "b" is pressed three successively times:

When letter "b" is pressed for the first time, the signal goes through the circuit and "A" is shown on screen. When the key is released, the rotor revolves one-letter-step to a different position that changes all the corresponding circuits so that each letter now has a different cryptograph. When letter "b" is pressed for the second time, the corresponding cryptograph is "C". So when letter "b" is pressed for the third time, the cryptograph is "E" according to the principle specified above.

Now the following figure shows the structure of a two-rotor Enigma.

The difference is that when a key is released, the second rotor won't revolve a step until the first one has finished one circle and returns to the original position. This is also the same in the case of three-rotor Enigma. That is: Only after the first rotor has finished one circle and return to the initial status, the second rotor will revolve a step. And only after the second rotor has finish one circle, the third rotor will revolve a step.

However, how did the Allied Forces obtain the information encrypted by Enigma? A person named Hans-Thilo Schimdt was very essential. He acted as a spy and provided the initial status of the three rotors in each Enigma to the Allied Forces once a month. The Allied Forces thus got everything they wanted by deciphering the intercepted cryptograph using the information offered by the spy.

Now, please design a program to obtain the plaintexts using the information offered by the Allied Forces.

Input

The input file contains several test cases representing several three-rotor Enigmas. The last test case in the input file is followed by a line containing a number 0.

Each case begins with a line containing an integer m (1 <= m <= 26) which indicates the number of sequential letters each rotor has. The first letter will always be A. (for example, m = 6 tells each rotor has 6 keys from A to F). The following three lines describe the initial status of the three rotors respectively. Each of them contains a string consisting of m capital character. For instance, a rotor with the initial status "BADFEC" indicates that the initial encrypt mechanism is to convert "abcdef" to "BADFEC", that is, original letter "a" corresponding to cryptograph letter "B", "b" to "A", "c" to "D", "d" to "F", "e" to "E" and "f" to "C". The forth line of each case contains an integer n which tells the number of cryptographs generated by the above Enigma. Then the following n lines are the n cryptographs respectively, which consist of m capital characters each.

Output

For each test case, the output should consist of two parts. The first line is the number of Enigma and a colon. The following lines are the plaintexts deciphered from the corresponding cryptographs. Each plaintext should be printed in one line. Note: The characters in the plaintext should be converted to the corresponding lowercases before they are printed.

Insert a blank line between test cases.

Sample Input

6
BADFEC
ABCDEF
ABCDEF
1
ACE
0

Output for the Sample Input

Enigma 1:
bbb

Hart is engaged in playing an interesting game, Gnome Tetravex, these days. In the game, at the beginning, the player is given n*n squares. Each square is divided into four triangles marked four numbers (range from 0 to 9). In a square, the triangles are the left triangle, the top triangle, the right triangle and the bottom triangle. For example, Fig. 1 shows the initial state of 2*2 squares.

Fig. 1 The initial state with 2*2 squares

The player is required to move the squares to the termination state. In the termination state, any two adjoining squares should make the adjacent triangle marked with the same number. Fig. 2 shows one of the termination states of the above example.

Fig. 2 One termination state of the above example

It seems the game is not so hard. But indeed, Hart is not accomplished in the game. He can finish the easiest game successfully. When facing with a more complex game, he can find no way out.

One day, when Hart was playing a very complex game, he cried out, "The computer is making a goose of me. It's impossible to solve it." To such a poor player, the best way to help him is to tell him whether the game could be solved. If he is told the game is unsolvable, he needn't waste so much time on it.

Input

The input file consists of several game cases. The first line of each game case contains one integer n, 0 <= n <= 5, indicating the size of the game.

The following n*n lines describe the marking number of these triangles. Each line consists of four integers, which in order represent the top triangle, the right triangle, the bottom triangle and the left triangle of one square.

After the last game case, the integer 0 indicates the termination of the input data set.

Output

You should make the decision whether the game case could be solved. For each game case, print the game number, a colon, and a white space, then display your judgment. If the game is solvable, print the string "Possible". Otherwise, please print "Impossible" to indicate that there's no way to solve the problem.

Print a blank line between each game case.

Note: Any unwanted blank lines or white spaces are unacceptable.

Sample Input

2
5 9 1 4
4 4 5 6
6 8 5 4
0 4 4 3
2
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
0

Output for the Sample Input

Game 1: Possible

Game 2: Impossible

Produce a table of the values of the series

Equation 1

for the 2001 values of x, x= 0.000, 0.001, 0.002, ..., 2.000. All entries of the table must have an absolute error less than 0.5e-12 (12 digits of precision). This problem is based on a problem from Hamming (1962), when mainframes were very slow by today's microcomputer standards.

Input

This problem has no input.

Output

The output is to be formatted as two columns with the values of x and y(x) printed as in the C printf or the Pascal writeln.

printf("%5.3f %16.12f\n", x, psix )  writeln(x:5:3, psix:16:12)

As an example, here are 4 acceptable lines out of 2001.

0.000   1.644934066848
...
0.500   1.227411277760
...
1.000   1.000000000000
...
2.000   0.750000000000

The values of x should start at 0.000 and increase by 0.001 until the line with x=2.000 is output.

Hint

The problem with summing the sequence in equation 1 is that too many terms may be required to complete the summation in the given time. Additionally, if enough terms were to be summed, roundoff would render any typical double precision computation useless for the desired precision.

To improve the convergence of the summation process note that

Equation 2

which implies y(1)=1.0. One can then produce a series for y(x) - y(1) which converges faster than the original series. This series not only converges much faster, it also reduces roundoff loss.

This process of finding a faster converging series may be repeated to produce sequences which converge more and more rapidly than the previous ones.

The following inequality is helpful in determining how may items are required in summing the series above.
Equation 3  

Cryptography deals with methods of secret communication that transform a message (the plaintext) into a disguised form (the ciphertext) so that no one seeing the ciphertext will be able to figure out the plaintext except the intended recipient. Transforming the plaintext to the ciphertext is encryption; transforming the ciphertext to the plaintext is decryption. Twisting is a simple encryption method that requires that the sender and recipient both agree on a secret key k, which is a positive integer.

The twisting method uses four arrays: plaintext and ciphertext are arrays of characters, and plaincode and ciphercode are arrays of integers. All arrays are of length n, where n is the length of the message to be encrypted. Arrays are origin zero, so the elements are numbered from 0 to n - 1. For this problem all messages will contain only lowercase letters, the period, and the underscore (representing a space).

The message to be encrypted is stored in plaintext. Given a key k, the encryption method works as follows. First convert the letters in plaintext to integer codes in plaincode according to the following rule: '_' = 0, 'a' = 1, 'b' = 2, ..., 'z' = 26, and '.' = 27. Next, convert each code in plaincode to an encrypted code in ciphercode according to the following formula: for all i from 0 to n - 1,

ciphercode[i] = (plaincode[ki mod n] - i) mod 28.

(Here x mod y is the positive remainder when x is divided by y. For example, 3 mod 7 = 3, 22 mod 8 = 6, and -1 mod 28 = 27. You can use the C '%' operator or Pascal 'mod' operator to compute this as long as you add y if the result is negative.) Finally, convert the codes in ciphercode back to letters in ciphertext according to the rule listed above. The final twisted message is in ciphertext. Twisting the message cat using the key 5 yields the following:

Your task is to write a program that can untwist messages, i.e., convert the ciphertext back to the original plaintext given the key k. For example, given the key 5 and ciphertext 'cs.', your program must output the plaintext 'cat'.

The input file contains one or more test cases, followed by a line containing only the number 0 that signals the end of the file. Each test case is on a line by itself and consists of the key k, a space, and then a twisted message containing at least one and at most 70 characters. The key k will be a positive integer not greater than 300. For each test case, output the untwisted message on a line by itself.

Note: you can assume that untwisting a message always yields a unique result. (For those of you with some knowledge of basic number theory or abstract algebra, this will be the case provided that the greatest common divisor of the key k and length n is 1, which it will be for all test cases.)

Example input:

5 cs.
101 thqqxw.lui.qswer
3 b_ylxmhzjsys.virpbkr
0

Example output: