Code Breaking

Time limit1sMemory limit128 MB

Summary

Decide whether some periodic permutation maps plaintext to ciphertext1, find the smallest valid period and permutation, then decrypt ciphertext2 with its inverse.

Level: Medium6 of 10
Topics: Implementation, Simulation, Brute force, String
Solved: No attempts yet

Problem

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.

Input

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 #.

Output

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.

Examples3

Example 1

Input

Mary had a little lamb!!
aMyrh daa l tilt ealbm!!
hTsii  s aetts
Foobar
blargg
No cycle
abc
bca
abcd
#

Expected output

This is a test
No cycle
cab?d?

Example 2
Input
```
hello
hello
world
#
```
Expected output
```
world
```
Example 3
Input
```
abcdef
badcfe
12345
#
```
Expected output
```
2143?5
```