Constructing Binary Strings with Exact Palindromic Substring Count

Given two positive integers \(n\) and \(k\) with \(k \le n\), you are to construct a binary string \(S\) of length \(n\) (i.e. a string consisting only of the characters '0' and '1') such that the number of distinct nonempty palindromic substrings of \(S\) is exactly \(k\).

A substring \(S[l;r]\) (with \(1 \le l \le r \le n\)) is the contiguous block of characters \(S_lS_{l+1}\ldots S_r\). A string \(T\) is a palindrome if \(T = T^T\) where \(T^T\) is the reverse of \(T\) (i.e. writing the characters of \(T\) in reverse order). Two substrings are considered essentially different if their contents differ.

A well known fact in combinatorics on words is that every binary string is rich in palindromes, meaning that any binary string of length \(n\) has exactly \(n\) distinct nonempty palindromic substrings (note: for \(n=1\) the unique string has one palindrome). Thus, under the binary alphabet, a valid string \(S\) exists if and only if either:

• \(n = 1\) and \(k = 1\), or
• \(n \ge 2\) and \(k = n\).

If the input does not satisfy one of these conditions then you should output impossible.

If a solution exists, you may output any valid string \(S\) satisfying the condition. A simple example when \(n \ge 2\) is to output the alternating string "0101…" of length \(n\), which is known to be rich.

inputFormat

The input consists of a single line containing two integers \(n\) and \(k\) (with \(k \le n\)).

outputFormat

If a valid binary string \(S\) exists, output any such string of length \(n\) whose number of distinct nonempty palindromic substrings is exactly \(k\). Otherwise, output impossible.

sample

1 1

0