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


-----Examples-----
Input
3 2
353

Output
3
353

Input
4 2
1234

Output
4
1313

Difficulty: competition

Starter code:

Solutions:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

n,k = list(map(int, input().split()))
a = list(map(int, input()))
b = a[:k]
c = [b[i%k] for i in range(n)]
if tuple(a)>tuple(c):
    d = int("".join(map(str, b)))
    d += 1
    b = list(map(int, str(d)))
    c = [b[i%k] for i in range(n)]
print(len(c))
print("".join(map(str, c)))



import sys

n, k = sys.stdin.readline().strip().split()
n = int(n)
k = int(k)
x = sys.stdin.readline().strip()
X = [0] * n
for i in range (0, n):
    X[i] = int(x[i])
v = 0
w = 0
for i in range (0, n):
    if v == 0 and (X[i] > X[i % k]):
        v = -1
    elif v == 0 and (X[i] < X[i % k]):
        v = 1
ans = []
if v == -1:
    i = k - 1
    while X[i] == 9:
        i = i - 1
    while i < k:
        X[i] = (X[i] + 1) % 10
        i = i + 1
for i in range (0, n):
    ans.append(str(X[i % k]))
print(n)
print("".join(ans))


n, k = list(map(int, input().split()))
s = input()

num = s[:k]*(n//k) + s[:n%k]

print(n)
if s <= num:
    print(num)
else:
    v = str(int(s[:k]) + 1)
    num  = v * (n//k)+ v[:n%k]
    print(num)



import sys
input = sys.stdin.readline

n,k=list(map(int,input().split()))
A=input().strip()


A+="0"*(k-n%k)

x=A[:k]
flag=0

for i in range(0,len(A),k):
    #print(int(A[i:i+k]))
    if A[i:i+k]>x:
        flag=1
        break
    elif A[i:i+k]==x:
        continue
    else:
        break

if flag==0:
    ANS=(x*(len(A)//k))[:n]
else:
    ANS=(str(int(x)+1)*(len(A)//k))[:n]

print(len(ANS))
print(ANS)
print()


import sys
input = sys.stdin.readline
 
n, k = list(map(int, input().split()))
a = list(input())
 
for i in range(n):
    a[i] = int(a[i])
 
for i in range(n):
    if a[i] < a[i % k]:
        b = [0] * n
        for i in range(n):
            b[i] = a[i % k]
        print(n)
        print("".join(map(str, b)))
        return
    if a[i] > a[i % k]:
        break
else:
    b = [0] * n
    for i in range(n):
        b[i] = a[i % k]
    print(n)
    print("".join(map(str, b)))
    return
 
for i in range(k)[::-1]:
    if i == k-1 and a[i] != 9:
        a[i] += 1
        break
    if a[i] == 9:
        a[i] = 0
    else:
        a[i] += 1
        break
for i in range(n):
    a[i] = a[i % k]
print(n)
print("".join(map(str, a)))


n, k = map(int, input().split())
a = input()
d = a[0:k]
c = int(d)
b=d*(n//k)
print(n)
b+=d[0:n%k]
if(b>=a):
    print(b)
else:
    c+=1
    d=str(c)
    b=d*(n//k)
    b+=d[0:n%k]
    print(b)