题目描述

小 $\rm S$ 是符文魔法师 , 他绘制了一种仅由字符 AB 组成的魔法符文

魔法符文每天都会变化

具体来说 , 每天开始时最左边的符文会改变类型 (即从 A 变为 B , 或从 B 变为 A , 取决于当天开始前的类型 )

其它每个符文仅在其左侧符文从 B 变为 A 时才会改变

例如 , 若初始符文排列为 ABBAA , 那么第二天开始时只有最左边的符文改变 , 序列变为 BBBAA

再过一天 , 最左边符文改变 , 随后左边第二个符文也会改变 (因为其左侧符文从 B 变为 A ) , 接着第三个符文也会改变！即在这天变化后 , 符文变为 AAABA

给出符文初始状态 $\rm M$ 和天数 $\rm D$ , 确定经过 $\rm D$ 天后符文的状态

输入格式

第一行输入字符串 $\rm M$ 与整数 $\rm D$ , 使用空格分隔

保证在 $\rm D$ 天后最右边的符文不会从 B 变为 A

输出一个字符串 , 表示从状态 $\rm M$ 开始经过 $\rm D$ 天后符文的状态

ABBA 2

AAAB

ABBBABBB 10

AAABBBBB

BBABBBBBBAABAABABAABBABBAAAAA 324987450

BABABBAAAABABBAAAAABBBAAAABAB

$\rm |M|$ 表示魔法符文的长度

对于 $60\%$ 的数据 $\rm 1 \leq D \leq 10^6$

对于 $100\%$ 的数据 $\rm 1 \leq |M| \leq 30 , 1 \leq D \leq 2^{30} -1$