#P1268A. Long Beautiful Integer

    ID: 3877 Type: RemoteJudge 3000ms 256MiB Tried: 0 Accepted: 0 Difficulty: 5 Uploaded By: Tags>constructive algorithmsgreedyimplementationstrings*1700

Long Beautiful Integer

Description

You are given an integer xx of nn digits a1,a2,,ana_1, a_2, \ldots, a_n, which make up its decimal notation in order from left to right.

Also, you are given a positive integer k<nk < n.

Let's call integer b1,b2,,bmb_1, b_2, \ldots, b_m beautiful if bi=bi+kb_i = b_{i+k} for each ii, such that 1imk1 \leq i \leq m - k.

You need to find the smallest beautiful integer yy, such that yxy \geq x.

The first line of input contains two integers n,kn, k (2n200000,1k<n2 \leq n \leq 200\,000, 1 \leq k < n): the number of digits in xx and kk.

The next line of input contains nn digits a1,a2,,ana_1, a_2, \ldots, a_n (a10a_1 \neq 0, 0ai90 \leq a_i \leq 9): digits of xx.

In the first line print one integer mm: the number of digits in yy.

In the next line print mm digits b1,b2,,bmb_1, b_2, \ldots, b_m (b10b_1 \neq 0, 0bi90 \leq b_i \leq 9): digits of yy.

Input

The first line of input contains two integers n,kn, k (2n200000,1k<n2 \leq n \leq 200\,000, 1 \leq k < n): the number of digits in xx and kk.

The next line of input contains nn digits a1,a2,,ana_1, a_2, \ldots, a_n (a10a_1 \neq 0, 0ai90 \leq a_i \leq 9): digits of xx.

Output

In the first line print one integer mm: the number of digits in yy.

In the next line print mm digits b1,b2,,bmb_1, b_2, \ldots, b_m (b10b_1 \neq 0, 0bi90 \leq b_i \leq 9): digits of yy.

Sample Input 1

3 2
353

Sample Output 1

3
353

Sample Input 2

4 2
1234

Sample Output 2

4
1313