题目内容

灯带车间要把一条只有暗格和亮格的样带拆成明暗交错的子序列，再按字典规矩挑出指定名次的那一条，写入当晚的工艺单。

样带是长度为 $m$ 的 $01$ 串 $b=b_1b_2\dots b_m$，其中 0 表示暗格，1 表示亮格。值班员会选出一组下标 $1 \le p_1 < p_2 < \dots < p_u \le m$（$u$ 可以为 0），按顺序拼成子序列 $g=b_{p_1}b_{p_2}\dots b_{p_u}$。

如果 $g$ 里没有相邻两格同暗或同亮，也就是对任意 $1 \le i < |g|$ 都有 $g_i \neq g_{i+1}$，就称 $g$ 是一条明暗交错带。

所有能得到明暗交错带的下标集合都算不同方案，即使拼出来的串相同也各记一次。把这些 $g$ 收成一个允许重复的序列，先按长度从短到长，长度相同时再按字典序（0 小于 1）排列。空串也参与排列。

请找出排列后的第 $q$ 条；如果没有第 $q$ 条，输出 -1。输入保证第 $q$ 条不会是空串。

询问组数与样带长度满足 $1 \le m \le$ 2000，$2 \le q \le$ 1000000000000000。

输入描述

第一行两个整数 $m$、$q$（$1 \le m \le$ 2000，$2 \le q \le$ 1000000000000000），表示样带长度和要取的名次。

第二行一个长度为 $m$ 的 $01$ 字符串 $b$。

输出描述

输出一行，即排列后的第 $q$ 条明暗交错带；若不存在，输出 -1。

样例1

输入

3 4
110

输出

1

说明

合法方案对应的串为：空串、两处单独的 1、一处 0、以及两条 10。按长度再字典序后是空串、0、1、1、10、10。第 4 条是 1。

样例2

输入

4 2
0101

输出

0

说明

空串最短，下一名是长度为 1 且字典序更小的 0。$q=2$，因此输出 0。

样例3

输入

1 5
0

输出

-1

说明

只有空串和 0 两条，没有第 5 条。