beecrowd | 2801

Affine Cipher

By Francisco Elio Parente Arcos Filho, UEA BR Brazil

Timelimit: 1

A cipher process consists in change each symbol of a message to another symbol from the same alphabet used in the original message, in the way to has one by one correspondence to each other. It means that two different symbols can not be replaced by the same symbol.

An Affine cipher consists in suppose some symbols of a T size alphabet as numbers of an interval [0..T-1]. Two positive numbers A and B are chosen. To cipher a symbol is necessary to multiply its position value on the alphabet by A and the number B needs to be added to the result of this multiplication. In the end, the result will be the position of the symbol that will replace the original in the sequence. If this new position does not correspond to a valid position inside the size of the alphabet, it supposes that the alphabet will be repeated many times on the right, in the way to have all estimated positions.

For example, suppose an alphabet which its size is 7 and A=4 and B=2. To cipher any symbol from this alphabet is necessary to extend the alphabet to the right by 3 times, as shown below:

In this cipher, the symbol 6 is ciphered to the symbol 5 because A x 6 + B=26 and the symbol in position 26 is 5.

Need to be noted that not all Affine cipher is valid. A poorly made cipher can not produce a one-by-one correspondence between symbols, not guaranteeing that the decipher could be made in a unique way.

Your task is, given the parameters A and B and the alphabet size, decipher a message with N symbols or show that it not possible to do so.


The first line of the input consists in an integer number N (1 ≤ N ≤ 105) that corresponds to the message size. The second line consists of N integer numbers Mi (0 ≤ Mi < T) that correspond to the message itself. The third line contains three integers: T (1 ≤ T ≤ 109) that corresponds to the alphabet size; and A (1 ≤ A ≤ 109) and B (1 ≤ B ≤ 109) as specified before.


The output consists in a single line containing the deciphered message, with its symbols separated by a single blank space, if will be possible to decipher each symbol of the alphabet in a single mode. Otherwise, print the message "DECIFRAGEM AMBIGUA" (ambiguous decipher).

Input Samples Output Samples


2 6 3 0 4 1 5

7 4 2

0 1 2 3 4 5 6


6 79 44

108 73 41

1 2 3


73 60 49

119 25 48

1 10 100