cho.shTime limit
2s
Memory limit
128 MB
Consider the following encryption method, which turns a plaintext into a ciphertext using a key. The plaintext, ciphertext, and key are all uppercase English strings with no spaces.
Let N be the length of the key. First, split the plaintext from left to right into groups of N characters and place each group as a row. For example, if the plaintext is MEETMEBYTHEOLDOAKTREENTH and the key is BATBOY, the table is arranged as follows.
| B | A | T | B | O | Y |
|---|---|---|---|---|---|
| M | E | E | T | M | E |
| B | Y | T | H | E | O |
| L | D | O | A | K | T |
| R | E | E | N | T | H |
The top row containing the key is shown only for explanation. Next, sort the columns stably by their key characters. In other words, the columns of BATBOY are ordered by the sorted key ABBOTY. If the same character appears multiple times, the column that was farther left in the original table comes first.
| A | B | B | O | T | Y |
|---|---|---|---|---|---|
| E | M | T | M | E | E |
| Y | B | H | E | T | O |
| D | L | A | K | O | T |
| E | R | N | T | E | H |
In this example, among the two B columns, the original left column (B)MBLR comes first. Reading the sorted table column by column from left to right, and within each column from top to bottom, produces the ciphertext. Thus the ciphertext for this example is EYDEMBLRTHANMEKTETOEEOTH.
Given the key and the ciphertext, write a program that recovers the original plaintext.
The first line contains the key. The second line contains the ciphertext.
Both strings consist only of uppercase English letters. The length of the ciphertext is always a multiple of the length of the key. The key has length at most 10, and the ciphertext has length at most 100.
Print the recovered plaintext on the first line.