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; }