← 返回题目列表

Codeforces · 628/C

C. 熊和绳子的距离

中文机器翻译题面 查看原题

Limak 是一只小北极熊。他喜欢漂亮的字符串——长度为n、仅由小写英文字母组成的字符串。

两个字母之间的距离定义为它们在字母表中的位置之间的差异。例如,$$\operatorname{dist}(c,e)=\operatorname{dist}(e,c)=2$$,$$\operatorname{dist}(a,z)=\operatorname{dist}(z,a)=25$$。

此外,两个好字符串之间的距离定义为对应字母的距离之和。例如,$$\operatorname{dist}(af,db)=\operatorname{dist}(a,d)+\operatorname{dist}(f,b)=3+4=7$$,$$\operatorname{dist}(\text{bear}, \text{roar}) = 16 + 10 + 0 + 0 = 26$$。

Limak 给你一个很好的字符串 s 和一个整数 k。他挑战你找到任何好的字符串 s' 且 $$\text{dist}(s, s') = k$$。找到满足给定条件的任何 s',如果不可能,则打印“-1”。

由于输入/输出可能达到巨大的尺寸,建议使用快速输入/输出方法:例如,在 C++ 中更喜欢使用 gets/scanf/printf 而不是 getline/cin/cout,在 Java 中更喜欢使用 BufferedReader/PrintWriter 而不是 Scanner/System.out。

输入

第一行包含两个整数 n 和 k (1 ≤ n ≤ 105, 0 ≤ k ≤ 106)。

第二行包含一个长度为n的字符串s,由小写英文字母组成。

输出

如果没有满足给定条件的字符串,则打印“-1”(不带引号)。

否则,打印任何 $$\text{dist}(s, s') = k$$ 的漂亮字符串 s'。

示例

输入 #1

4 26
bear

输出 #1

roar

输入 #2

2 7
af

输出 #2

db

输入 #3

3 1000
hey

输出 #3

-1