#P1268A. Long Beautiful Integer
-
ID: 3877
Type: RemoteJudge
3000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: 5
Uploaded By:
Hydro
Tags> Long Beautiful Integer
Description
You are given an integer $x$ of $n$ digits $a_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 < n$.
Let's call integer $b_1, b_2, \ldots, b_m$ beautiful if $b_i = b_{i+k}$ for each $i$, such that $1 \leq i \leq m - k$.
You need to find the smallest beautiful integer $y$, such that $y \geq x$.
The first line of input contains two integers $n, k$ ($2 \leq n \leq 200\,000, 1 \leq k < n$): the number of digits in $x$ and $k$.
The next line of input contains $n$ digits $a_1, a_2, \ldots, a_n$ ($a_1 \neq 0$, $0 \leq a_i \leq 9$): digits of $x$.
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, \ldots, b_m$ ($b_1 \neq 0$, $0 \leq b_i \leq 9$): digits of $y$.
Input
The first line of input contains two integers $n, k$ ($2 \leq n \leq 200\,000, 1 \leq k < n$): the number of digits in $x$ and $k$.
The next line of input contains $n$ digits $a_1, a_2, \ldots, a_n$ ($a_1 \neq 0$, $0 \leq a_i \leq 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, \ldots, b_m$ ($b_1 \neq 0$, $0 \leq b_i \leq 9$): digits of $y$.
3 2
353
4 2
1234
3
353
4
1313