spoj#PERMCODE. Permutation Code

Permutation Code

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

</p> 
               <td valign="top" style="font-family: monospace;">E<br>
               </td>
               <td valign="top" style="font-family: monospace;">A<br>
               </td>
               <td valign="top" style="font-family: monospace;">R<br>
               </td>
               <td valign="top" style="font-family: monospace;"><br>

               </td>
               <td valign="top" style="font-family: monospace;"><br>
               </td>
               <td valign="top"><br>
               </td>
             </tr>
             <tr>
            <td valign="top"><span style="font-style: italic;">M</span>

=
</td> 

            </td>
            <td valign="top" style="font-family: monospace;">T<br>
            </td>
            <td valign="top" style="font-family: monospace;">E<br>
            </td>
            <td valign="top" style="font-family: monospace;">R<br>
            </td>

            <td valign="top"><br>
            </td>
          </tr>
          <tr>
               <td valign="top"><br>
               </td>
               <td valign="top"><br>
               </td>
               <td valign="top"><br>

               </td>
               <td valign="top"><br>
               </td>
               <td valign="top"><br>
               </td>
               <td valign="top"><br>
               </td>
               <td valign="top"><br>
               </td>

               <td valign="top"><span style="font-style: italic;"></span><br>
             </td>
             </tr>
             <tr>
            <td valign="top"><span style="font-style: italic;">C</span>

=
</td> 

            </td>
            <td valign="top" style="font-family: monospace;"><br>
            </td>
            <td valign="top" style="font-family: monospace;"><br>
            </td>
            <td valign="top" style="font-family: monospace;"><br>
            </td>
            <td valign="top" style="font-family: monospace;"><br>
            </td>

            <td valign="top" style="font-family: monospace;"><br>
            </td>
            <td valign="top"><span style="font-style: italic;"></span><span style="font-style: italic;">M</span>[0] is <span style="font-family: monospace;">T</span>, <span style="font-family: monospace;">T</span> is at <span style="font-style: italic;">P</span>[0]. <span style="font-style: italic;">M</span>[1] is <span style="font-family: monospace;">E</span>, <span style="font-family: monospace;">E</span> is at <span style="font-style: italic;">S</span>[3]. <span style="font-style: italic;">C</span>[0] = <span style="font-style: italic;">S</span>[0 xor 3] = <span style="font-style: italic;">S</span>[3]<br>

            </td>
          </tr>
          <tr>
            <td valign="top"><br>
            </td>
            <td valign="top" style="font-family: monospace;">E<br>
            </td>
            <td valign="top" style="font-family: monospace;">T<br>

            </td>
            <td valign="top" style="font-family: monospace;"><br>
            </td>
            <td valign="top" style="font-family: monospace;"><br>
            </td>
            <td valign="top" style="font-family: monospace;"><br>
            </td>
            <td valign="top" style="font-family: monospace;"><br>
            </td>

            <td valign="top"><span style="font-style: italic;">M</span>[1]

is E, E is at P[1]. M[2] is E, E is at S[3]. C[1] = S[1 xor 3] = S[2]

            </td>
          </tr>
          <tr>
            <td valign="top"><br>
            </td>
            <td valign="top" style="font-family: monospace;">E<br>
            </td>
            <td valign="top" style="font-family: monospace;">T<br>

            </td>
            <td valign="top" style="font-family: monospace;">A<br>
            </td>
            <td valign="top" style="font-family: monospace;"><br>
            </td>
            <td valign="top" style="font-family: monospace;"><br>
            </td>
            <td valign="top" style="font-family: monospace;"><br>

            </td>
            <td valign="top"><span style="font-style: italic;"></span><span style="font-style: italic;">2 is d. M</span>[2] is <span style="font-family: monospace;">E</span>, <span style="font-family: monospace;">E</span> is at <span style="font-style: italic;">P</span>[1], so <span style="font-style: italic;">C</span>[2] =&nbsp; <span style="font-style: italic;">S</span>[1]<br>

            </td>
          </tr>
          <tr>
            <td valign="top"><br>
            </td>
            <td valign="top" style="font-family: monospace;">E<br>
            </td>
            <td valign="top" style="font-family: monospace;">T<br>

            </td>
            <td valign="top" style="font-family: monospace;">A<br>
            </td>
            <td valign="top" style="font-family: monospace;">E<br>
            </td>
            <td valign="top" style="font-family: monospace;"><br>
            </td>
            <td valign="top" style="font-family: monospace;"><br>

            </td>
            <td valign="top"><span style="font-style: italic;">M</span>[3]

is T, T is at P[0]. M[4] is E, E is at S[3]. C[3] = S[0 xor 3] = S[3]

            </td>
          </tr>
          <tr>
            <td valign="top"><br>
            </td>
            <td valign="top" style="font-family: monospace;">E<br>
            </td>
            <td valign="top" style="font-family: monospace;">T<br>

            </td>
            <td valign="top" style="font-family: monospace;">A<br>
            </td>
            <td valign="top" style="font-family: monospace;">E<br>
            </td>
            <td valign="top" style="font-family: monospace;">A<br>
            </td>

            <td valign="top" style="font-family: monospace;"><br>
            </td>
            <td valign="top"><span style="font-style: italic;">M</span>[4]

is E, E is at P[1]. M[5] is R, R is at S[0]. C[4] = S[1 xor 0] = S[1]

            </td>
          </tr>
          <tr>
            <td valign="top"><br>
            </td>
            <td valign="top" style="font-family: monospace;">E<br>
            </td>
            <td valign="top" style="font-family: monospace;">T<br>

            </td>
            <td valign="top" style="font-family: monospace;">A<br>
            </td>
            <td valign="top" style="font-family: monospace;">E<br>
            </td>
            <td valign="top" style="font-family: monospace;">A<br>
            </td>

            <td valign="top" style="font-family: monospace;">A<br>
            </td>
            <td valign="top"><span style="font-style: italic;">M</span>[5]

is R, R is at P[3]. M[0] is T, T is at S[2]. C[5] = S[3 xor 2] = S[1]

            </td>
          </tr>


    </tbody>

  </table>

  <div style="margin-left: 40px;"> </div>
      <br>

       I have included additional examples of encrypted messages at the

end of this note for you to experiment with. However, first, I need to tell you about the decryption algorithm.</td>

</p> 
  <p>I, Albert Charles Montgomery, have just discovered the most amazing
cypher for encrypting messages. Let me tell you about it.&nbsp;<br>
       </p>



  <p>To begin, you will need to decide on a set of symbols, call it <span style="font-style: italic;">S</span>,   perhaps with the letters <span style="font-family: monospace;">RATE</span>. The size of this set must be

a power of 2 and the order of the symbols in S is important. You must note that R is at position 0, A at 1, T at 2, and E at 3. You will also need one permutation P of all those symbols, say TEAR. Finally you will need an integer, call it x. Together, these make up the key. Given a key, you are now ready to convert a plaintext message M of length n (M[0], M[1]... M[n-1]), that has some but not necessarily all of the symbols in S, into a cyphertext string C, also of length n (C[0], C[1],...C[n-1]), that has some but not necessarily all of the symbols in S. 

       </p>

  <p>The encrypting algorithm computes <span style="font-style: italic;">C</span> as follows:</p>

  <ol>
     <li>Calculate an integer <span style="font-style: italic;">d</span> as the remainder after dividing the

integer part of (n1.5

  • x) by n. This can be expressed more succinctly as d = (int)(n1.5 + x) % n, where "%" is the remainder operator.

    • </p> 
      <li>   Set <span style="font-style: italic;">C</span>[<span style="font-style: italic;">d</span>] to be the symbol in <span style="font-style: italic;">S</span> whose position is the  same   as the
    </li>

position of M[d] in P.

     </li>
     <li>    For each <span style="font-style: italic;">j</span> ≠ <span style="font-style: italic;">d</span> in 0..<span style="font-style: italic;">n</span>-1,
          set <span style="font-style: italic;">C</span>[<span style="font-style: italic;">j</span>] to be the symbol in <span style="font-style: italic;">S</span> whose position is the  value   obtained

by xor-ing the position of M[j] in P with the position of M[(j+1) % n] in S. Note that the bitwise xor operator is "^" in C, C++, and Java. </li>

  </ol>

For example, consider this scenario where S=RATE, P=TEAR, x=102, M=TEETER, and n=6. To compute d, first calculate 61.5 + 102 = 116.696938, then take the remainder after dividing by 6. So d = 116 % 6 = 2. The following table shows the steps in filling in the cyphertext C. Note that the order of the steps is not important.

  <table cellpadding="2" cellspacing="2" border="1" style="text-align: left; width: 90%; margin-left: 40px;">
        <tbody>
          <tr>
            <td valign="top"><br>
            </td>
            <td valign="top">0<br>
            </td>
            <td valign="top">1<br>

            </td>
            <td valign="top">2<br>
            </td>
            <td valign="top">3<br>
            </td>
            <td valign="top">4<br>
            </td>

            <td valign="top">5<br>
            </td>
            <td valign="top"><br>
            </td>
          </tr>
          <tr>
               <td valign="top"><span style="font-style: italic;">S</span>

=

               </td>
               <td valign="top" style="font-family: monospace;">R<br>
               </td>
               <td valign="top" style="font-family: monospace;">A<br>
               </td>
               <td valign="top" style="font-family: monospace;">T<br>
               </td>

               <td valign="top" style="font-family: monospace;">E<br>
               </td>
               <td valign="top" style="font-family: monospace;"><br>
               </td>
               <td valign="top" style="font-family: monospace;"><br>
               </td>
               <td valign="top"><br>
               </td>

             </tr>
             <tr>
               <td valign="top"><span style="font-style: italic;">P</span>

=

T
 T
 E
 E
 E

Unfortunately, the next page of the note, with the decrypting algorithm, is completely unreadable because it is covered with huge, overlapping, messy ink blots. Given your considerable skill in unravelling puzzles, your task is to write the decoder based on your knowledge of the encoding algorithm.

Input

The input for the decoder consists of one or more sets of {key, encrypted message} pairs. The key is on 3 separate lines. The first line contains the single integer x, 0 < x < 10,000; the second line contains the string S; and the third line contains the string P, which will be a permutation of S. The length of S (and therefore P) will always be one of the following powers of two: 2, 4, 8, 16, or 32. Following the key is a line containing the encrypted message string C, which will contain at least one and at most sixty characters. The strings S, P, and C will not contain whitespace, but may contain printable characters other than letters and digits. The end of the input is a line which contains the single integer 0.

Output

For each input set print the decrypted string on a single line, as shown in the sample output.

Example

Input:
102
RATE
TEAR
ETAEAA
32
ABCDEFGHIJKLMNOPQRSTUVWXYZ._!?,;
;ABCDEFGHIJKLMNOPQRSTUVWXYZ._!?,
MOMCUKZ,ZPD
1956
ACEHINT_
ACTN_IHE
CIANCTNAAIECIA_TAI
0

Output:
TEETER
HELLO_WORLD
THE_CAT_IN_THE_HAT
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  2. © 2021-2024 Hydro.ac
  4. Worker 1 in 326ms
  5. Hydro v4.18.0 Professional