DMOPC '20 Contest 4 P5 - Cyclic Cypher

View as PDF

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 16M
Java 32M
Python 64M

Author:
Problem type

You are working as a cryptographer in a post-apocalyptic world. The most common form of information is transmitted in messages with cyclic arrays of size where each element is either or , taking inspiration from the previously failed binary system. To ensure that the message is not corrupted, the receiver of the message uses an identification number . The message can be verified if the sum of the products of elements in every cyclic subarray of length is . You would like to send a valid message to a recipient with identification number . Please find any valid message that can be verified, or determine that no such message exists.

Constraints

If and are expressed as and respectively where and are odd and and are integers, then .

Input Specification

The first and only line contains integers and , as specified in the problem statement.

Output Specification

If it is impossible to create a valid message, output 0. Otherwise, output space-separated integers (either or ) on a single line, representing the cyclic array.

Note: your output must follow the standard convention of not having any leading or trailing whitespace, and it must end with a new line.

Sample Input

8 3

Sample Output

-1 -1 1 1 -1 1 -1 1

Explanation

The diagram below shows the cyclic array, with the indices labeled below the elements.

The following list shows the product of every cyclic subarray of length :

The product of elements from index to is .
The product of elements from index to is .
The product of elements from index to is .
The product of elements from index to is .
The product of elements from index to is .
The product of elements from index to is .
The product of elements from index to is .
The product of elements from index to is .

Summing, we get , so this message can be verified. Note that this is not the only possible solution, and other verifiable messages will also be accepted.