The Vegenère cipher is a famous cipher which uses a keyboard to shift the value of each character of the message by some amount. For example, if the message is
HELLOWORLD, and the keyword is
CODE, then the Vegenère cipher first repeats the keyword until its the same length as the message, then encrypts the message by "adding" the two strings together:
HELLOWORLD + CODECODECO = KTPQRLSWOS
To add the strings together, we "shift" each character in the message by the character in the keyword. For example, shifting
Z, shifting by
A, shifting by
B, and so on. Note that the shift wraps around the alphabet, i.e.
A is after
Alice and Bob have been spreading rumours behind Eve's back. They do not want Eve to find out, so they have encrypted their messages using the Vegenère cipher. However, they have made a fatal flaw by choosing an English word as their keyword and only sending messages consisting of English words. Can you help Eve decipher what they are saying?
The standard input will contain 10 datasets. Each dataset begins with an integer ~N~ ~(1 \le N \le 10^5)~, the number of words in the English dictionary that Alice and Bob are using. ~N~ lines follow, each containing a word in the English language. The total size of the dictionary will be at most ~10^6~ characters.
The next line contains the encrypted message, which will be at most ~10^5~ characters in length.
All strings in the input will consist of upper-case English characters.
For 30% of the cases, ~N \le 10~ and the encrypted string will contain at most two words. For 60% of the cases, ~N \le 100~.
For each dataset, output the first ten characters of the decrypted message and the sum of the squared lengths of the words in the message. If there are multiple solutions, output the one that comes first alphabetically. If there are multiple interpretations of a message, output the one that minimizes the sum of squared lengths of the words in the message.
Sample Input (Two Datasets Shown)
3 CODE HELLO WORLD KTPQRLSWOS 5 EVE IS VERY COOL SILLY HKTUVKTDBHXXON
HELLOWORLD 50 EVEISVERYS 54
Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org