Cody 写下了一个由英文字母组成的字符串和一个整数 $k$。现在他想要变换这个字符串，使得它恰好有 $k$ 个“孔”。孔是指字母中封闭的环。例如，字母 “B” 有两个孔，而字母 “a” 有一个孔。

Cody 可以通过选择一个字母并将其“递增”来变换字符串，即将其变为字母表中的下一个字母（对于字母表中的最后一个字母，下一个字母是字母表中的第一个字母）。Cody 可以对字符串中的任意字母重复此操作任意次数。

在 Cody 的理解中，字母表是以下英文字母序列：

AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz

所有 Cody 写下的字母看起来与上面描绘的字母表中的字母完全一样。

自然地，Cody 希望通过尽可能少的递增次数来实现他的目标。如果字符串无法被变换为包含所需数量的“孔”，Cody 看到了这一点，就不会进行任何变换。你能像 Cody 一样聪明吗？

输入格式

第一行包含两个空格分隔的整数 $n$ 和 $k$：字符串的长度和所需的“孔”数量（$1 \le n \le 10^5$，$ -10^{18} \le k \le 10^{18}$）。

第二行是 Cody 写下的字符串 $s$。字符串 $s$ 仅包含大小写英文字母。

输出格式

输出实现目标所需的递增次数，如果不可能实现，则输出 $-1$。

如果字符串可以被变换，第二行输出应该是变换后的字符串。如果有多种可能的答案，输出其中任意一个即可。

样例

输入格式 1

5 3
zlEna

输出格式 1

2
zlenB