Decryption of cyclic string shift

Swift Hard strings

任务 «Decryption of cyclic string shift»

给定一个加密字符串 S，由小写拉丁字母组成。它是通过将原始字符串 T 循环右移若干位置 k（0 ≤ k < |T|），然后将每个字符替换为字母表中的下一个字符（循环转换：'z' → 'a'）得到的。需要找到长度最小的原始字符串 T，使得经过上述变换后得到 S。如果存在多个这样的 T，则选择字典序最小的一个。S 的长度为 1 到 1000。保证存在解。

输入格式

一行字符串 S（小写拉丁字母，长度从 1 到 1000）。

输出格式

一行 — 原始字符串 T，具有最小长度（且在长度最小的字符串中按字典序最小）。

示例

示例 1

输入

za

输出

yz

示例 2

输入

aaa

输出

z

示例 3

输入

5
3
0

输出

None

main.swift