Magic Bitstrings

时间： 1ms 内存：128M

描述：

A bitstring, whose length is one less than a prime, might be magic. 1001 is one such string. In order to see the magic in the string let us append a non-bit x to it, regard the new thingy as a cyclic string, and make this square matrix of bits

each bit   1001

every 2^nd bit   0110

every 3^rd bit   0110

every 4^th bit   1001

This matrix has the same number of rows as the length of the original bitstring. The m-th row of the matrix has every m-th bit of the original string starting with the m-th bit. Because the enlarged thingy has prime length, the appended x never gets used.

If each row of the matrix is either the original bitstring or its complement, the original bitstring is magic.

Each line of input (except last) contains a prime number p ≤ 100000. The last line contains 0 and this line should not be processed. For each prime number from the input produce one line of output containing the lexicographically smallest, non-constant magic bitstring of length p-1, if such a string exists, otherwise output Impossible.

输入：

输出：

示例输入：

示例输出：

0110
01
0010111001110100
0000100001101010001101100100111010100111101111
Impossible
001001100001011010000001001111001110101010100011000011011111101001011110011011

提示：

参考答案：

解锁文章