Code Breaking

A periodic permutation is a simple encryption technique. You choose a period $k$ and a permutation of the first $k$ positions. To encrypt a message, split it into groups of $k$ characters (padding the final group if necessary) and reorder each group according to the permutation. To decrypt, take groups of $k$ characters and apply the inverse permutation.

For example, with $k = 4$ the permutation 2431 encrypts Mary into yMra. Applying the same permutation to Maryan (padded to Mary + an??) gives yMra?a?n, where ? marks a padding character.

Once the permutation is known, applying its inverse to any ciphertext produced with the same scheme recovers the original plaintext.

Write a program that reads (plaintext, ciphertext1, ciphertext2) triples. For each (plaintext, ciphertext1) pair, decide whether a periodic permutation could have transformed the plaintext into ciphertext1. If so, determine the period $k$ and the permutation, then apply the inverse permutation to ciphertext2 to recover its plaintext.

The input is a series of (plaintext, ciphertext1, ciphertext2) triples, one string per line. No line is longer than 80 characters. Within a triple the first two strings have the same length $n$ and give the first $n$ characters of the plaintext and of the ciphertext; there is no guarantee that $n$ is a multiple of $k$. The input ends with a line containing a single #.

For each triple, output one line. If a periodic permutation whose period is at most the length of the plaintext and ciphertext1 strings transforms the plaintext into ciphertext1, apply its inverse permutation to ciphertext2, padding with ? where necessary, and print the result. If no such permutation exists, print ciphertext2 unchanged. When several periods work, use the smallest period $k$; for the smallest period the matching permutation is always unique.