W's Cipher

Interview

Time limit1sMemory limit128 MB

Summary

Decrypt messages by extracting each of three character groups and rotating its subsequence right by the matching key.

Level: Easy3 of 10
Topics: String, Implementation, Simulation
Solved: No attempts yet

Problem

A family of memory-constrained wireless devices is too small to run standard encryption, so it uses the following lightweight cipher instead. Implement it.

Encryption uses three integer keys $k_1$ , $k_2$ , $k_3$ . The characters are split into three groups: the letters [a-i] form the first group, [j-r] the second, and everything else ([s-z] and the underscore _) the third. Take only the characters of one group, in the left-to-right order they appear in the message: encryption rotates this subsequence left by $k_i$ positions and writes the rotated characters back into the same positions. Each group is rotated independently, and rotating one group never moves any character of another group.

Decryption reverses this: within each group, rotate the subsequence right by $k_i$ positions.

For example, the message the_quick_brown_fox encrypted with keys $k_1=2$ , $k_2=3$ , $k_3=1$ becomes _icuo_bfnwhoq_kxert. To decrypt, look at the [a-i] characters of the ciphertext. They are i, c, b, f, h, e, occupying (1-indexed) positions 2, 3, 7, 8, 11, 17. A right rotation by $k_1=2$ puts h, e, i, c, b, f into those positions. The table below shows the message after decrypting each group in turn.

Step	Rotated group	Before	After
1	`[a-i]`, right by $k_1=2$	`_icuo_bfnwhoq_kxert`	`_heuo_icnwboq_kxfrt`
2	`[j-r]`, right by $k_2=3$	`_heuo_icnwboq_kxfrt`	`_heuq_ickwbro_nxfot`
3	`[s-z]` and `_`, right by $k_3=1$	`_heuq_ickwbro_nxfot`	`the_quick_brown_fox`

Given the keys and a ciphertext, output the decrypted message.

Input

Every string consists only of lowercase letters and underscores (_) and is at most 80 characters long. Each $k_i$ is an integer between 1 and 100 inclusive.

The input contains one or more encrypted messages. Each message is given as two lines: the first line holds the three keys $k_1$ , $k_2$ , $k_3$ separated by spaces, and the second line is the encrypted message. The input ends with a line 0 0 0 (all keys zero), which is not processed.

Output

For each encrypted message, print the decrypted string on its own line.

Examples2

Example 1

Input

2 3 1
_icuo_bfnwhoq_kxert
1 1 1
bcalmkyzx
3 7 4
wcb_mxfep_dorul_eov_qtkrhe_ozany_dgtoh_u_eji
2 4 3
cjvdksaltbmu
0 0 0

Expected output

the_quick_brown_fox
abcklmxyz
the_quick_brown_fox_jumped_over_the_lazy_dog
ajsbktcludmv

Example 2
Input
```
1 1 1
bcdefghia
0 0 0
```
Expected output
```
abcdefghi
```