Due on: 27th of December 2009 Question 1: This question is taken from the ACM programming competition. Leonardo Da Vinci, the famous inventor and artist, was fond of cryptography and has invented many devices and techniques to hide messages. One such invention is the cryptex. A cryptex is a small device used to carry a secret message and is made of one or more rings. Each ring has the 26 uppercase letters written in some random order. It is by aligning these rings in one specific way that the secret message is revealed. The secret message is made of two words, each of length N. The first word of the secret message is called the unlocking word and the second is called the secret word. To properly align the cryptex, you need to know the unlocking word. Once you have the cryptex and the unlocking word, all you have to do is align the rings on the cryptex to spell the unlocking word. The letters on the rings, though randomly ordered, are arranged in such a way that when the cryptex is aligned to spell the unlocking word, one of the other 25 strings would spell the secret word. To reveal the secret message you’ll need to know at least one letter from the secret word. Take for example the following cryptex made of five rings (each line constitutes a ring:) KFZLQMDWJUSHGCEIXRAOPNVTYB IMWZPFJBKLTNOEQDHUXGVYASRC FAMIETZORWPSQUNGLDYBKXHCVJ XNAKVPICQHDFWEGBRTMLZOUSYJ ZSYFDOWIJCAKPBTXLRUNGQMVHE The unlocking word is “GREEN” and we know that the second letter of the secret word is “P”. By aligning the rings to spell the unlocking word, the cryptex now looks like this: GCEIXRAOPNVTYBKFZLQMDWJUSH RCIMWZPFJBKLTNOEQDHUXGVYAS ETZORWPSQUNGLDYBKXHCVJFAMI EGBRTMLZOUSYJXNAKVPICQHDFW NGQMVHEZSYFDOWIJCAKPBTXLRU The secret word is revealed by looking for the word whose second letter is ’P’. Input Format Your program will be tested on one or more test cases. The first line of the input specifies a single integer D which represents the number of test cases. Each test case is specified using N +1 lines. The first line of each test case has the following format: NUS N is a positive integer which is the number of rings. No cryptex will have more than 1000 rings. U is the unlocking word while S describes the secret word. S is made of N characters, all underscore characters (’_’) except exactly one. For example, having S equal to "_ P _ _ _" says that the second letter of the secret word is "P". The remaining N lines specifies the N rings, one on each line. Each line is made of (different) 26 uppercase letters. Consecutive test cases are separated by a single blank line. Output Format For each test case, write on a separate line, the unlocking word, followed by the secret word, separated by a single space.