Progressive Scramble

Interview

Time limit2sMemory limit512 MB

Summary

Encrypt a message by cumulative sums of symbol values mod 27, and decrypt by inverting the same recurrence.

Level: Easy3 of 10
Topics: Implementation, Math, String, Prefix sum
Solved: No attempts yet

Problem

You belong to a naive spy agency. To keep its traffic private, the agency uses a very simple encryption algorithm that changes each symbol of a message progressively, based on the symbols before it. The allowed symbols are the space and the 26 lowercase English letters. For encryption they are given the values 0 (for a space) and 1 through 26 (for a to z). Write $v(s)$ for the numeric value of symbol $s$ .

Consider a message with symbols $s_1, s_2, \dots, s_n$ . The algorithm first turns the leading symbol $s_1$ into its value $u_1 = v(s_1)$ . Then, for every following symbol $s_i$ , it computes $u_i = v(s_i) + u_{i-1}$ , the sum of that symbol's value and the computed value of the previous symbol. (When the message holds a space, the previously scrambled letter appears once more.) The process repeats until every $u_i$ is known.

At this point the message is a sequence of numbers. To print it, convert it back to symbols. Since there are 27 valid symbols, take $u_i$ modulo 27 and replace that value with the matching symbol. For example, if $u_i = 32$ , then $32 \bmod 27 = 5$ , and the symbol is e because $v(e) = 5$ .

Encrypting the string "my pie" goes like this.

Turn each symbol $s_i$ into $v(s_i)$ : [13, 25, 0, 16, 9, 5]
Compute each $u_i$ : [13, 38, 38, 54, 63, 68]
Take each $u_i$ modulo 27: [13, 11, 11, 0, 9, 14]
Convert back to symbols: "mkk in"

Write a program that encrypts text with this algorithm and also decrypts text that was encrypted with it.

Input

The first line holds one integer $n$ ( $1 \le n \le 100$ ). Each of the next $n$ lines holds the letter e or d, a single space, and then a message that runs to the end of the line. A message is made of lowercase English letters and spaces only, and its length is between 1 and 80 characters. The letter e means encrypt the string that follows, and d means decrypt it.

Output

For each message in the input, print the result of encrypting or decrypting it on its own line. Differences in whitespace matter in this problem. Your output must match the correct output character for character, spaces included.

Examples2

Example 1

Input

7
e testing multiple letters rrrrrrrrrrrrr
e this particularly long  sentence can test encryption
d tajbbrsjcloiuvmywwhwjqqqinauzmpuuxyllejbvv nqhfvoxlz
e my pie
d mkk in
e the quick brown fox jumps over the lazy dog
d taffwqzbmmofuqddjyvvezlatthchzzs eeqrqoosgn

Expected output

tyqjsfmmzteygwhmmycwpulddvmdvmdvmdvmdv
tajbbrsjcloiuvmywwhwjqqqinauzmpuuxyllejbvv nqhfvoxlz
this particularly long  sentence can test encryption
mkk in
my pie
taffwqzbmmofuqddjyvvezlatthchzzs eeqrqoosgn
the quick brown fox jumps over the lazy dog

Example 2
Input
```
2
e my pie
d mkk in
```
Expected output
```
mkk in
my pie
```