题目内容

在一片远古遗迹中，发现了一块刻满魔法符文的石板。符文分为两类：天符文（对应大写字母 A-Z）和地符文（对应小写字母 a-z）。石板每个月会经历一次魔力波动，每次波动中，两类符文各自独立演化：天符文会向左移动一位，即变为字母表中的前一个字母，且 A 的前一位为 Z；地符文则会根据当前月序 $i$（从 $1$ 开始）向右移动 $i$ 位，即变为字母表中后数第 $i$ 个字母，z 的后一位为 a。

现在考古学家记录了石板上原始的符文序列 $s$，并想知道经过 $k$ 个月后，石板上呈现的最终符文序列。由于直接逐月模拟时间开销过大，你可以利用总位移量来计算：天符文经过 $k$ 个月的总偏移为 $-k \bmod 26$，地符文的总偏移为 $\sum_{i=1}^{k} i = \frac{k(k+1)}{2} \bmod 26$。

约束：符文序列的长度 $|s|$ 满足 $1 \le |s| < 10^6$，且仅由大写和小写英文字母组成。月数 $k$ 满足 $1 \le k \le 10^6$。

输入描述

第一行输入一个仅由大写和小写英文字母组成的字符串 $s$，其长度满足 $1 \le |s| < 10^6$。 第二行输入一个整数 $k$，表示经过的月数，满足 $1 \le k \le 10^6$。

输出描述

输出一个字符串，表示经过 $k$ 个月演变后石板上的符文序列。

样例1

输入

HelloZ
1

输出

GfmmpY

说明

对于 $k = 1$，大写字母总偏移 $U = (-1) \bmod 26 = 25$（相当于左移 1 位），小写字母总偏移 $S = \frac{1 \times 2}{2} \bmod 26 = 1$。

• H (大写) 左移 1 位变为 G。
• e (小写) 右移 1 位变为 f。
• l (小写) 右移 1 位变为 m。
• l (小写) 右移 1 位变为 m。
• o (小写) 右移 1 位变为 p。
• Z (大写) 左移 1 位变为 Y（Z 的前一位为 Y）。

因此最终序列为 GfmmpY。

样例2

输入

zoo
2

输出

crr

说明

对于 $k = 2$，大写总偏移无应用，小写总偏移 $S = \frac{2 \times 3}{2} \bmod 26 = 3$。

• z 右移 3 位：z 变为 a 变为 b 变为 c，最终为 c。
• o 右移 3 位：o 变为 p 变为 q 变为 r，最终为 r。
• 第二个 o 同理变为 r。

最终结果为 crr。

样例3

输入

AZ
26

输出

AZ

说明

当 $k = 26$ 时，大写字母总偏移 $U = (-26) \bmod 26 = 0$，大写字母保持不变。序列中没有小写字母，因此整体序列不变。实际上小写偏移 $S = \frac{26 \times 27}{2} \bmod 26 = 13$，但此处无小写字母受影响。故输出仍为 AZ。

样例4

输入

AbCd
5

输出

VqXs

说明

对于 $k = 5$，大写总偏移 $U = (-5) \bmod 26 = 21$，小写总偏移 $S = \frac{5 \times 6}{2} \bmod 26 = 15$。

• A (大写) 偏移 21：A + 21 = V。
• b (小写) 偏移 15：b + 15 = q。
• C (大写) 偏移 21：C + 21 = X。
• d (小写) 偏移 15：d + 15 = s。

最终序列为 VqXs。