Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Long Beautiful Integer

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

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

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

Examples

Input

3 2 353

Output

3 353

Input

4 2 1234

Output

4 1313

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/25/2021 21:12:57 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|