Description

Deep within the Crimson Demon Village lies an ancient sealed ruin, and Megumin has decided to break the seal out of sheer curiosity! Her first attempt, of course, was to blast it with Explosion, which did absolutely nothing. Lying exhausted on the ground afterward (as usual), she finally noticed an inscription carved into the seal: a string consisting of lowercase English letters. Legend says the seal will only open when this inscription is recited in its encrypted form. Help her unlock it by computing the encryption , defined recursively as follows:

• denotes the length of , denotes the empty string, and denotes string concatenation.
• is the middle character of , i.e., the character at index (0-indexed). If is even, is the left one of the two middle characters.
• and are obtained by splitting at :
  • is the substring to the left of .
  • is the substring to the right of .
  • Neither nor contains itself, and either of them may be empty.
• shifts the lowercase letter forward by positions in the alphabet, wrapping around from z back to a (e.g., ). Formally, it is the character whose ASCII code is , where is the ASCII code of a.

For example, if the inscription is :

Enc("quiz") = shift('u', 4) + Enc("q") + Enc("iz")
Enc("q")    = shift('q', 1) + Enc("") + Enc("")  = "r"
Enc("z")    = shift('z', 1) + Enc("") + Enc("")  = "a"   (wraps around from z to a)
Enc("iz")   = shift('i', 2) + Enc("") + Enc("z") = "k" + "" + "a" = "ka"
Enc("quiz") = shift('u', 4) + "r" + "ka" = "y" + "r" + "ka" = "yrka"

Input

A single line containing the string .

Constraints

• consists only of lowercase English letters (a–z).

Subtasks

• Subtask 1 (Testcase 1-5): , and consists only of the letters a through m (so no wrap-around occurs).
• Subtask 2 (Testcase 6-10): No additional constraints.

Output

Output a single line containing the string .

Sample Input  Download

Sample Output  Download

Discuss