题目描述

佳佳有许多黑色和白色的小珠子，他最喜欢用它们穿成一串串漂亮的项链了。

他的每条项链都是由不超过 $n$ 个小珠子串在一起的环（称项链上的珠子数为项链的长度），每条项链至少有一个珠子。每做完一条项链就在其中的某一个珠子上贴一个标签，从贴有标签的那颗珠子开始，顺时针记录每个珠子的颜色（白色用 0 表示，黑色用 1 表示）。标签上写着这种记录。

佳佳发现，这样做，每条项链都可以用多个标签来表示，例如图 (a) 的项链，当标签分别贴在珠子 $1,2,3,4$ 的时候，标签上应分别写作 0100，1000，0001 和 0010。

在这样的情况下，佳佳总是选择字典序最小的一个串写在标签上。例如图 (a) 的项链，在珠子 $3$ 处帖上标签 0001。

再考虑图 (b) 所示的项链，最小字典序的标签串是 0101，可是标签应该贴在哪颗珠子上呢？珠子 $1$ 上还是珠子 $3$ 上呢？佳佳不希望出现这样的情况。所以他在做项链的时候格外小心，保证做出来的项链是合法的（也就是不会出现标签位置不唯一的情况）。

这样，标签上的记录就可以标识一个串。根据标签上串的字典序就可以对项链进行排序，例如图 (c) 的项链比图 (d) 的小，因为 00101 的字典序比 0011 小。

任务一：新年快到了，佳佳决定给自己的两个双胞胎表妹一人做一条项链。刚做完其中一条项链后，佳佳突然有了一个绝妙的想法：既然是送给孪生姐妹，为什么不做一对“孪生项链”呢？换句话说，如果把所有可能的项链排好顺序，“孪生项链”的位置应当是相邻的，姐姐的项链标签的字典序要比妹妹的大。佳佳想把已经做好的一条项链送给妹妹，那么姐姐的项链应该是什么样子的呢？

任务二：佳佳还想知道所有合法的项链中长度恰好为 $k$ 的有多少条，你能告诉他吗？

输入格式

第 $1$ 行包含三个整数 $n,m,k$ ，相邻整数用一个空格隔开。

其中 $n$ 表示每条项链的珠子数上限，$m$ 表示任务一中妹妹的项链长度，$k$ 表示任务二中的项链长度。

第 $2$ 行包括一个长度为 $m$ 的 01 串，表示妹妹的项链上的标签。

输入数据保证无误。

输出格式

第 $1$ 行一个正整数 $t$，表示长度恰好为 $k$ 的项链有 $t$ 条；

第 $2$ 行一个 01 串，表示姐姐的项链上的标签。

输入数据保证姐姐的项链一定可以做出来。

5 5 5
00101

6
0011

样例说明

项链可能有以下 $14$ 种：0，00001，0001，00011，001，00101，0011，00111，01，01011，011，0111，01111，1。

其中长度为 $1,2,3,4,5$ 的项链分别有 $2,1,2,3,6$ 个。

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 2\times 10^5$，$1\leq k\leq 10^3$，$1\leq m, k\leq n$。