Permutation Code

As the owner of a computer forensics company, you have just been handed the following note by a new client.

I, Albert Charles Montgomery, have discovered a wonderful cipher for encrypting messages. Let me explain it.

First, choose a set of symbols S — for example the letters RATE. The size of S must be a power of two, and the order of the symbols matters: in RATE, R is at position 0, A at 1, T at 2, and E at 3. You also need one permutation P of the symbols of S, say TEAR, and an integer x. Together, (S, P, x) form the key.

A plaintext message M has length n; its characters are M[0], M[1], ..., M[n-1], each taken from S (not necessarily every symbol of S, and repetition is allowed). Encryption turns M into a ciphertext C of the same length n, also made of symbols of S.

Let posS(c) be the position of a character c inside S, and posP(c) its position inside P. Encryption builds C as follows:

1. Compute the pivot index d = floor(n^1.5 + x) mod n — the integer part of n^1.5 + x, taken modulo n.
2. Set C[d] = S[posP(M[d])].
3. For every j with 0 <= j < n and j != d, set C[j] = S[posP(M[j]) XOR posS(M[(j+1) mod n])], where XOR is the bitwise exclusive-or of the two position numbers.

For example, consider S = RATE, P = TEAR, x = 102, and M = TEETER (so n = 6). Since n^1.5 + x = 116.69..., we get d = 116 mod 6 = 2. The order of the steps does not matter; the table below fills in every position of C.

So TEETER encrypts to ETAEAA.

Unfortunately, the next page of the note — the one describing the decryption algorithm — is completely covered by ink blots and cannot be read. Using your knowledge of the encryption algorithm, write the decoder: given a key (S, P, x) and a ciphertext C, recover the original plaintext M. The plaintext is uniquely determined by the key and the ciphertext.

The input contains one or more datasets, each a {key, encrypted message} pair.

Each key occupies three lines:

• the first line is the integer x with 0 < x < 10000;
• the second line is the string S;
• the third line is the string P, a permutation of S.

The length of S (and therefore of P) is one of the powers of two 2, 4, 8, 16, or 32. The key is followed by one line holding the ciphertext C, whose length is between 1 and 60 characters. The strings S, P, and C contain no whitespace, but may contain printable characters other than letters and digits.

The input ends with a line containing the single integer 0.

For each dataset, print the decrypted plaintext string on its own line.