Long Beautiful Integer

题意翻译

### 题目描述 给定一个由 $a_1, a_2, \ldots, a_n$ 从左到右构成的整数 $x$ 和一个正整数 $k$。 若由 $b_1, b_2, \ldots, b_m$ 从左到右构成的整数满足 $\forall i \in [1,m-k], b_i=b_{i+k}$，则称其为美丽数。 请求出最小的由 $b_1, b_2, \ldots, b_m$ 从左到右构成的美丽数 $y$，满足 $y \geq x$。 ### 输入格式 第一行两个整数 $n,k$，其中 $n$ 表示 $x$ 的位数，$k$ 的含义如题所述。 下一行包含由 $a_1, a_2, \ldots, a_n$ 从左到右构成的 $n$ 位整数 $x$，数据保证不包含前导零。 ### 输出格式 第一行输出一个整数 $m$，表示答案 $y$ 的位数。 下一行输出由 $b_1, b_2, \ldots, b_m$ 从左到右构成的 $m$ 位整数 $y$，不包含前导零。 ### 数据范围 $2 \leq n \leq 2 \times 10^5$，$1 \leq k \leq n$。

题目描述

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

输入输出样例

输入样例 #1

3 2
353

输出样例 #1

3
353

输入样例 #2

4 2
1234

输出样例 #2

4
1313