题目描述

winter_l 和 Lost_Memory 正在玩一个游戏。最初，winter_l 有一个字符串 $s$ = "a"。

给定一个正整数 $k$ 和一个长度为 $n$，只包含 $0$ 和 $1$ 的序列 $a_1, a_2, a_3 \cdots a_n$，其中 $a_i$ 表示第 $i$ 次操作的类型。

现在 Lost_Memory 将要求 winter_l 按顺序执行所有操作：

• 如果 $a_i = 0$，将 $s$ 的一份副本追加到它自身。

• 如果 $a_i = 1$，将 $s$ 中的每个字符更改为英文字母表中的下一个字符来生成一个新字符串，并将其追加到原始的 $s$。例如，对 "c" 进行操作生成 "cd"，对 "zb" 进行操作生成 "zbac"。

在执行所有操作后，输出 $s$ 中第 $k$ 个字符的值。

注意，在第二种类型的操作中，字符 'z' 可以变成 'a'。

题目保证输入保证在执行所有操作后，$s$ 至少有 $k$ 个字符

输入格式

第一行，两个正整数 $k, n$，意义如题所示

接下来一行，一个长度为 $n$ 的 $01$ 序列

输出格式

在执行所有操作后，输出 $s$ 中第 $k$ 个字符

输入输出样例

5 3
0 0 0

a

10 4
0 1 0 1

b

提示

样例解释

第一个样例

最初，word == "a"。winter_l 按以下方式执行三次操作：

将 "a" 附加到 "a"，word 变为 "aa"。

将 "aa" 附加到 "aa"，word 变为 "aaaa"。

将 "aaaa" 附加到 "aaaa"，word 变为 "aaaaaaaa"。

第二个样例

最初，word == "a"。winter_l 按以下方式执行四次操作：

将 "a" 附加到 "a"，word 变为 "aa"。

将 "bb" 附加到 "aa"，word 变为 "aabb"。

将 "aabb" 附加到 "aabb"，word 变为 "aabbaabb"。

将 "bbccbbcc" 附加到 "aabbaabb"，word 变为 "aabbaabbbbccbbcc"。

数据规模