Long Beautiful Integer

3000ms

262144K

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$$$.

3 2
353

3
353

4 2
1234

4
1313

Informação

Provedor Codeforces

Código CF1268A