Let $s$ be some string consisting of symbols "0" or "1". Let's call a string $t$ a substring of string $s$, if there exists such number $1 \leq l \leq |s| - |t| + 1$ that $t = s_l s_{l+1} \ldots s_{l + |t| - 1}$. Let's call a substring $t$ of string $s$ unique, if there exist only one such $l$. 

For example, let $s = $"1010111". A string $t = $"010" is an unique substring of $s$, because $l = 2$ is the only one suitable number. But, for example $t = $"10" isn't a unique substring of $s$, because $l = 1$ and $l = 3$ are suitable. And for example $t =$"00" at all isn't a substring of $s$, because there is no suitable $l$.

Today Vasya solved the following problem at the informatics lesson: given a string consisting of symbols "0" and "1", the task is to find the length of its minimal unique substring. He has written a solution to this problem and wants to test it. He is asking you to help him.

You are given $2$ positive integers $n$ and $k$, such that $(n \bmod 2) = (k \bmod 2)$, where $(x \bmod 2)$ is operation of taking remainder of $x$ by dividing on $2$. Find any string $s$ consisting of $n$ symbols "0" or "1", such that the length of its minimal unique substring is equal to $k$.


-----Input-----

The first line contains two integers $n$ and $k$, separated by spaces ($1 \leq k \leq n \leq 100\,000$, $(k \bmod 2) = (n \bmod 2)$).


-----Output-----

Print a string $s$ of length $n$, consisting of symbols "0" and "1". Minimal length of the unique substring of $s$ should be equal to $k$. You can find any suitable string. It is guaranteed, that there exists at least one such string.


-----Examples-----
Input
4 4

Output
1111
Input
5 3

Output
01010
Input
7 3

Output
1011011



-----Note-----

In the first test, it's easy to see, that the only unique substring of string $s = $"1111" is all string $s$, which has length $4$.

In the second test a string $s = $"01010" has minimal unique substring $t =$"101", which has length $3$.

In the third test a string $s = $"1011011" has minimal unique substring $t =$"110", which has length $3$.

Difficulty: HARD
Tags: String algorithms

Mathematics

Constructive algorithms

Starter code:

Solutions:
(n, k) = [int(i) for i in input().split()]
print('1' * n if k == n else (('0' * ((n - k) // 2) + '1') * (n // ((n - k) // 2) + 1))[0:n])


(n, k) = map(int, input().strip().split())
d = (n - k) // 2 + 1
x = ['1' if (i + 1) % d == 0 else '0' for i in range(n)]
print(''.join(x))


(n, k) = [int(x) for x in input().split()]
ans = ''
while len(ans) < n:
	ans += '1' * ((n - k) // 2) + '0'
ans = ans[:n]
print(ans)


d = [int(x) for x in input().split()]
(n, k) = (d[0], d[1])
a = (n - k) // 2
for i in range(n):
	print('1' if (i + 1) % (a + 1) == 0 else '0', end='')


(n, k) = list(map(int, input().split()))
x = (n - (k - 1) + 1) // 2
STR = '0' * (x - 1) + '1'
ANS = STR * (n // x + 1)
print(ANS[:n])


(n, k) = map(int, input().split())
a = (n - k) // 2
s = '0' * a + '1'
print(s * (n // (a + 1)) + s[:n % (a + 1)])


(n, k) = map(int, input().split())
a = (n - k) // 2
ps = '0' * a + '1'
s = ''
i = 0
while i + a + 1 <= n:
	s += ps
	i += a + 1
if i < n:
	x = n - i
	s += ps[:x]
print(s)


(N, K) = map(int, input().split())
if K == 0 or N == K:
	print('1' * N)
elif K == 1:
	print('0' + '1' * (N - 1))
elif K <= 2 // N:
	if K & 1:
		print('10' * (K // 2 + 1) + '1' * (N - 2 - K // 2 * 2))
	else:
		print('0' + '10' * (K // 2) + '1' * (N - 1 - K // 2 * 2))
else:
	print((('0' + '1' * ((N - K) // 2)) * (N // ((N - K) // 2) + 1))[:N])


(n, k) = map(int, input().split())
if n == k:
	print('1' * n)
	return
a = n - k >> 1
i = 0
Ans = ''
while i < n:
	Ans += '0' * a
	i += a
	if i > n - 1:
		break
	Ans += '1'
	i += 1
	if i > n - 1:
		break
print(Ans[:n])


(n, k) = map(int, input().split())
d = n - k
d = d // 2
l = []
while n > 0:
	i = min(n, d)
	while i > 0:
		l.append('1')
		i -= 1
		n -= 1
	if n > 0:
		l.append('0')
		n -= 1
print(''.join(l))


import math
import sys
(n, k) = list(map(int, input().split()))
a = [0] * n
side = (n - k) // 2
for i in range(side, n, side + 1):
	a[i] = 1
print(''.join(map(str, a)))


(n, k) = list(map(int, input().split()))
chuj_twojej_starej = (n - k) // 2 + 1
i = 1
while True:
	if i % chuj_twojej_starej == 0:
		print(0, end='')
	else:
		print(1, end='')
	if i == n:
		break
	i += 1


(n, k) = map(int, input().split())
if n == k:
	print('1' * n)
else:
	print((('0' * ((n - k + 2) // 2 - 1) + '1') * (n // ((n - k + 2) // 2) + 1))[:n])


(n, k) = list(map(int, input().split()))
e = (n - k) // 2
c = '0' * e + '1'
while len(c) <= n:
	c = c + c
print(c[:n])


(N, K) = map(int, input().split())
if N == K:
	print('0' * N)
elif K == 1:
	print('0' * (N - 1) + '1')
elif K == 3:
	print('1' + '0' * (N - 4) + '101')
else:
	res = ['0'] * N
	for i in range(0, N, N // 2 - K // 2 + 1):
		res[i] = '1'
	print(''.join(res))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math
(n, k) = map(int, input().split())
a = (n - k) // 2
s = ''
while len(s) < n:
	s = s + '0' * a + '1'
print(s[:n])


(n, k) = map(int, input().split())
if n == k:
	print('1' * n)
elif k == 1:
	print('0' + '1' * (n - 1))
else:
	x = (n - k) // 2
	a = '0' * x + '1'
	print(a * (n // (x + 1)) + '0' * (n % (x + 1)))


(n, e) = map(int, input().split())
d = (n - e) // 2
q = []
while n > 0:
	i = min(n, d)
	while i > 0:
		q.append('1')
		i -= 1
		n -= 1
	if n > 0:
		q.append('0')
		n -= 1
print(''.join(q))


(n, k) = map(int, input().split())
if k == 1:
	print('1' + '0' * (n - 1))
else:
	t = (n - k) // 2
	a = ''.join(['0' + '1' * t] * (n // (t + 1)))
	if len(a) < n:
		a += '0'
	print(a + '1' * (n - len(a)))


t = 1

def solve():
	k1 = (n - k) // 2
	for i in range(n):
		print(int((i + 1) % (k1 + 1) == 0), end='')
	print()
for _ in range(t):
	(n, k) = map(int, input().split())
	solve()


(n, k) = map(int, input().split())
if k == 1:
	print('1', end='')
	for i in range(1, n):
		print('0', end='')
	print()
	exit()
a = (n + k - 2) // 2
ans = ''
if (a - k + 2) % 2:
	for i in range(a - k + 2):
		ans += chr(i % 2 + 48)
else:
	ans += chr(48)
	for i in range(1, a - k + 2):
		ans += chr(49)
for i in range(a - k + 2, n):
	ans += ans[i - a + k - 2]
print(ans)


(n, k) = map(int, input().split())
x = (n - k) // 2
f = '0' * x + '1'
f = f * (n // (x + 1) + 1)
print(f[:n])


import sys
input = sys.stdin.readline

def solve():
	(n, k) = map(int, input().split())
	if k == 1:
		print('0' * (n - 1) + '1')
		return
	z = (n - k) // 2 + 1
	s = ''.join(['0' if i % z == 0 else '1' for i in range(n)])
	print(s)
solve()


(n, k) = map(int, input().split())
d = (n - k) // 2
s = 0
while s != n:
	if (s + 1) % (d + 1) == 0:
		print('1', end='')
	else:
		print('0', end='')
	s += 1


(n, k) = map(int, input().split())
diff = (n - k) // 2
if diff == 0:
	print('1' * n)
else:
	rep = '1' * diff + '0'
	long = rep * (200000 // diff + 1)
	print(long[:n])


from math import *
from fractions import *

def li():
	return list(map(int, input().split(' ')))
(n, k) = li()
if k == 1:
	print('1' + '0' * (n - 1))
else:
	a = (n - k) // 2
	p = '1' + '0' * a
	ans = p * (n // (a + 1)) + p[:n % (a + 1)]
	print(ans)


import os
import sys

def log(*args, **kwargs):
	if os.environ.get('CODEFR'):
		print(*args, **kwargs)
(n, k) = tuple(map(int, input().split()))
s = '0' * ((n - k) // 2) + '1'
for i in range(n):
	print(s[i % len(s)], end='')
print()


(N, K) = [int(x) for x in input().split()]
len = (N - K) // 2 + 1
s0 = '0' * (len - 1) + '1'
print(s0 * (N // len) + s0[:N % len])


from sys import stdin
(n, m) = map(int, stdin.readline().strip().split())
x = n - m
x = x // 2
s = ''
y = 0
if m == 1:
	print('0' + (n - 1) * '1')
	exit(0)
while len(s) < n:
	if y == 1:
		s += '1' * x
	else:
		s += '0'
	y += 1
	y = y % 2
print(s[0:n])


(n, k) = map(int, input().split())
length = (n - k + 2) // 2
string = '0' * (length - 1) + '1'
answer = string * (n // length + 1)
print(answer[:n])


(n, k) = map(int, input().split())
(s, v) = ((n - k) // 2 * '0' + '1', '')
while len(v) < n:
	v += s
print(v[:n])


import sys
from math import *
from fractions import gcd
readints = lambda : map(int, input().strip('\n').split())

def hasUnique(s, n, k):
	freq = {}
	for i in range(n - k + 1):
		x = s[i:i + k]
		if x not in freq:
			freq[x] = 0
		freq[x] += 1
	for k in freq:
		if freq[k] == 1:
			return True
	return False

def good(s, n, k):
	for i in range(1, k):
		if hasUnique(s, n, i):
			return False
	freq = {}
	for i in range(n - k + 1):
		x = s[i:i + k]
		if x not in freq:
			freq[x] = 0
		freq[x] += 1
	st = set()
	for x in freq:
		if freq[x] == 1:
			if len(st) > 0:
				return False
			st.add(x)
	return len(st) == 1

def gen(i, s, n, k):
	if i == n:
		if good(s, n, k):
			print(s)
	else:
		gen(i + 1, s + '0', n, k)
		gen(i + 1, s + '1', n, k)
(n, k) = readints()
if n == k:
	print('0' * n)
	sys.exit(0)
s = ''
while len(s) < n:
	r = int((n - k) // 2)
	s = s + ('0' * r + '1')
s = s[:n]
print(s)


(n, k) = map(int, input().split())
if k == 1:
	print('1' + '0' * (n - 1))
	exit(0)
dist = (n - k) // 2
s = '1' + dist * '0'
for i in range(n // len(s)):
	print(s, end='')
print(s[0:n % len(s)])


(n, k) = map(int, input().split())
print((((n - k) // 2 * '0' + '1') * (n // ((n - k) // 2 + 1) + 1))[:n])


from collections import *
from math import *
(n, k) = map(int, input().split())
x = (n - k) // 2 + 1
for i in range(1, n + 1):
	if i % x == 0:
		print(1, end='')
	else:
		print(0, end='')
print()


(n, m) = map(int, input().split())
a = (n - m) // 2
a1 = ''
for i in range(a):
	a1 += '0'
ans = ''
last = a1
while len(ans) <= n:
	if last == a1:
		ans += a1
		last = '1'
	else:
		ans += last
		last = a1
for i in range(n):
	print(ans[i], end='')


(n, k) = map(int, input().split())
if n == k:
	print('1' * n)
elif k == 1:
	print('1' + '0' * (n - 1))
else:
	t = []
	while len(t) < n:
		t += '1' + '0' * ((n - k) // 2)
	for x in t[:n]:
		print(x, sep='', end='')


(n, k) = map(int, input().split())
strr = ''
while len(strr) < n:
	strr += '0' * ((n - k) // 2) + '1'
strr = strr[:n]
print(strr)