Jiajia has many black and white beads, and he loves to string them into beautiful necklaces. Each of his necklaces is a ring formed by at most $n$ beads (the number of beads on the necklace is called the length of the necklace), and each necklace has at least one bead. After making a necklace, he attaches a label to one of the beads. Starting from the bead with the label, he records the color of each bead in clockwise order (white is represented by 0, black by 1). The label displays this record.

(a) Necklace 0001 (b) An invalid necklace (c) Necklace 00101 (d) Necklace 0011

Jiajia discovered that with this method, each necklace can be represented by multiple labels. For example, for the necklace in figure (a), when the label is attached to beads 1, 2, 3, and 4, the labels should be written as 0100, 1000, 0001, and 0010, respectively. In such cases, Jiajia always chooses the string with the lexicographically smallest order to write on the label. For example, for the necklace in figure (a), the label 0001 is attached at bead 3.

Now consider the necklace shown in figure (b). The lexicographically smallest label string is 0101, but which bead should the label be attached to? Bead 1 or bead 3? Jiajia does not want this situation to occur. Therefore, he is extra careful when making necklaces to ensure that the necklaces produced are legal (meaning there is no ambiguity in the label position).

In this way, the record on the label can identify a string. Based on the lexicographical order of the strings on the labels, necklaces can be sorted. For example, the necklace in figure (c) is smaller than the necklace in figure (d) because the lexicographical order of 00101 is smaller than 0011.

Task 1: New Year is coming, and Jiajia decides to make one necklace for each of his two twin cousins. After finishing one of the necklaces, Jiajia suddenly had a brilliant idea: since they are twin sisters, why not make a pair of "twin necklaces"? In other words, if all possible necklaces are sorted, the "twin necklaces" should be adjacent in position, and the lexicographical order of the elder sister's necklace label should be greater than the younger sister's. Jiajia wants to give the necklace he has already made to the younger sister; what should the elder sister's necklace look like?

Task 2: Jiajia also wants to know how many legal necklaces have a length exactly equal to $k$. Can you tell him?

Input

The first line of the input file twins.in contains three integers $n$, $m$, and $k$ ($1 \le m, k \le n$), separated by spaces, where $n$ represents the upper limit of the number of beads on each necklace; $m$ represents the length of the younger sister's necklace in Task 1; and $k$ represents the necklace length in Task 2. The second line contains a 01 string of length $m$, representing the label on the younger sister's necklace. The input data is guaranteed to be correct.

Output

The first line of the output file twins.out contains a positive integer $t$, representing the number of necklaces with length exactly $k$. The second line contains a 01 string representing the label on the elder sister's necklace. It is guaranteed that the elder sister's necklace can be constructed.

Examples

Input 1

5 5 5
00101

Output 1

6
0011

Note

The possible necklaces are the following 14 types: 0, 00001, 0001, 00011, 001, 00101, 0011, 00111, 01, 01011, 011, 0111, 01111, 1 Among these, the number of necklaces with lengths 1, 2, 3, 4, and 5 are 2, 1, 2, 3, and 6, respectively.