Long Beautiful Integer

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

3 2
353

output

3
353

input

4 2
1234

output

4
1313

Solution:

#include <bits/stdc++.h>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
string s;
cin >> s;
cout << n << '\n';
  string t = s.substr(0, k);
  for (int i = k; i < n; i++) {
    t += t[i - k];
  }
  if (t >= s) {
cout << t << '\n';
  } else {
    for (int i = k - 1; i >= 0; i--) {
if (t[i] == '9') {
t[i] = '0';
} else {
++t[i];
break;
}
}
for (int i = k; i < n; i++) {
      t[i] = t[i - k];
    }
    cout << t << '\n';
  }
  return 0;
}