题目描述

有一种字符串加密算法使用递归方式进行加密，加密规则如下：

若字符串长度为 1，则加密结果为原字符串

否则，将字符串分为前半部分与后半部分（如果长度为奇数，前半部分比后半部分多 1 个字符）

分别对前半部分和后半部分进行递归加密

最终加密结果为：后半部分加密结果 + 前半部分加密结果 例如，对于字符串 "abcd"：

分为 "ab" 和 "cd"

"ab" 加密后为 "ba"

"cd" 加密后为 "dc"

最终结果为 "dcba"

再例如，对于字符串 "abcde"：

分为 "abc" 和 "de"

"abc" 加密：分为 "ab" 和 "c"，"ab" 加密为 "ba"，所以 "abc" 加密结果为 "cba"

"de" 加密为 "ed"

最终结果为 "edcba"

请你实现这个加密算法，对给定字符串进行加密。

输入格式

输入一个仅包含小写字母的字符串，长度不超过 1000。

输出格式

输出加密后的字符串。

输入输出样例

输入

abcd

输出

bcda