Under construction

Still being built. Things may change

Leapfrog Encryption

Time limit1sMemory limit2048 MB

Summary
Given a key and a text, the task encrypts plaintext or decrypts ciphertext by alternately filling empty cells at key-defined skip intervals.
Level

Medium4 of 10

Topics
Implementation, Simulation, String
Solved
No attempts yet

Problem

We have come up with a new encryption method called Leapfrog Encryption. It is a key-based scheme where an alphabetic key specifies how letters in the plaintext (the text to be encrypted) are placed in the ciphertext (the resulting encrypted string). Leapfrog Encryption works as follows:

  1. Remove all non-alphabetic characters from the plaintext and convert all remaining letters to lowercase.
  2. Convert each letter of the key to its position in the alphabet +1+ 1 ('a' becomes 2, 'b' becomes 3, and so on). This gives a sequence of numbers d1,d2,…,dnd_1, d_2, \ldots, d_n, where nn is the length of the key.
  3. Going left-to-right, place the first letters of the plaintext in every d1d_1-th position of the ciphertext until you run out of positions. The length of the ciphertext equals the number of letters in the plaintext. For example, if d1=5d_1=5, the first letter of the plaintext goes in position 5 of the ciphertext (counting the first position as 1), the second letter goes in position 10, and so on.
  4. Repeat this with d2d_2, but going right-to-left through the ciphertext. Only count the empty positions, so you leapfrog over letters already placed.
  5. Continue with d3d_3, d4d_4, and so on, alternating the direction each time.
  6. If letters remain in the plaintext after using dnd_n, fill the remaining empty positions with these letters, going in the opposite direction of the previous pass (this is equivalent to dn+1=1d_{n+1} = 1).

For example, take the plaintext "Send more monkeys!" and the key "bea". The encryption proceeds as follows:

b →\rightarrow 3, left-to-right:_ _ s _ _ e _ _ n _ _ d _ _ m
e →\rightarrow 6, right-to-left:_ _ s _ _ e o _ n _ _ d _ _ m
a →\rightarrow 2, left-to-right:_ r s _ e e o _ n m _ d o _ m
last pass, right-to-left:s r s y e e o e n m k d o n m

Decryption is left for you to figure out.

Input

The first line contains two strings tt and kk. tt is either E or D, meaning encrypt or decrypt. kk is the lowercase alphabetic key, with length between 1 and 100, inclusive.

The second and final line contains the plaintext to encrypt (if tt is E) or the ciphertext to decrypt (if tt is D). The string is non-empty and has at most 2,000 characters. A ciphertext consists of lowercase letters only. A plaintext may also contain uppercase letters, numbers, punctuation, and spaces, all of which count toward the length. A plaintext is guaranteed to contain at least one letter.

Output

Output the encrypted or decrypted text. The output contains only lowercase letters.

Examples3

  1. Example 1

    Input
    E bea
    Send more monkeys!
    
    Expected output
    srsyeeoenmkdonm
    
  2. Example 2

    Input
    D bea
    srsyeeoenmkdonm
    
    Expected output
    sendmoremonkeys
    
  3. Example 3

    Input
    D zyxwvutsrqponmlkjihgfedcba
    lafogrpe
    
    Expected output
    leapfrog