Olimpiada Informatyczna

IX Olimpiada Informatyczna 2001/2002

Task: szy

Author: Szyfr

Cipher

III stage contest

We are given a sequence of positive integers a_i (for i=1,2,...,n). This sequence is used to encrypt n-bit messages. If we have a message consisting of consecutive bits (t₁,...,t_n) (t_i is either 0 or 1), then its encryption it the number:

S=t₁a₁+t₂a₂+...+t_na_n

Task

You are given encrypted messages and sequences of numbers (a_i), that have been used to encrypt the messages. Your task is to decrypt the encrypted messages and to save them in particular files. You are not expected to present any program. It is sufficient that you write the decrypted messages.

Input

You are given several sets of data at your disposal. Each set is written in a separate file: szyk.in, where k is the number of the set. In the first line of each file there is one integer n, 5<=n<=40. In the successive n lines there is a sequence of numbers (a_i) written: in the line of number i+1 there is one positive integer a_i. The sum of the numbers a_i does not exceed 2 000 000 000. In the line of number n+2 there is one integer S - the encrypted message, 0<=S<=a₁+a₂+...+a_n.

Output

For each set of data szy*.in you should create a file szy*.out containing the decrypted message. In the first line of this file you should write the successive numbers t_i, without any spaces between them. The test data were chosen so that the encrypted messages are unambiguously determined.

Example

For the following input file szy.in:

the correct answer is in the following output file szy.out:

110001000101101100010101