[codeforces1158B]The minimal unique substring

time limit per test : 1 second memory limit per test : 256 megabytes

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\le l\le |s|-|t|+1$ that $t=s_l{s}_{l+1}\dots 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$ $mod$ $2)=(k$ $mod$ $2)$, where $(x$ $mod$ $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\le k\le n\le 100000,(k$ $mod$ $2)=(n$ $mod$ $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.

题意： 给定两个数字$n,k$,他们奇偶性相同，要求构造一个长度为$n$的01串$s$，使得$s$所有长度小于$k$的子串在$s$中都不止出现一次。保证有解。

题解： 首先我们设$l=(n-k)/2$ 因为解一定存在，而且必定为$s_{l+1}...s_{n-l}$ 那么接下来就很好理解了，这样如下划分可以让$1$到$k-1$长度的字符串都出现重复。 我们只要在每个$((n-k)/2+1)\ast q(q>=n)$处放置一个0其他位置都是1即可。

#include<bits/stdc++.h> #define LiangJiaJun main using namespace std; int n,k; int LiangJiaJun(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ printf("%d",(i%((n-k)/2+1)>0)); } puts(""); return 0; }