#D1542. Long Beautiful Integer
Long Beautiful Integer
Long Beautiful Integer
You are given an integer x of n digits a_1, a_2, …, a_n, which make up its decimal notation in order from left to right.
Also, you are given a positive integer k < n.
Let's call integer b_1, b_2, …, b_m beautiful if b_i = b_{i+k} for each i, such that 1 ≤ i ≤ m - k.
You need to find the smallest beautiful integer y, such that y ≥ x.
Input
The first line of input contains two integers n, k (2 ≤ n ≤ 200 000, 1 ≤ k < n): the number of digits in x and k.
The next line of input contains n digits a_1, a_2, …, a_n (a_1 ≠ 0, 0 ≤ a_i ≤ 9): digits of x.
Output
In the first line print one integer m: the number of digits in y.
In the next line print m digits b_1, b_2, …, b_m (b_1 ≠ 0, 0 ≤ b_i ≤ 9): digits of y.
Examples
Input
3 2 353
Output
3 353
Input
4 2 1234
Output
4 1313
inputFormat
Input
The first line of input contains two integers n, k (2 ≤ n ≤ 200 000, 1 ≤ k < n): the number of digits in x and k.
The next line of input contains n digits a_1, a_2, …, a_n (a_1 ≠ 0, 0 ≤ a_i ≤ 9): digits of x.
outputFormat
Output
In the first line print one integer m: the number of digits in y.
In the next line print m digits b_1, b_2, …, b_m (b_1 ≠ 0, 0 ≤ b_i ≤ 9): digits of y.
Examples
Input
3 2 353
Output
3 353
Input
4 2 1234
Output
4 1313
样例
3 2
353
3
353