Codeforces Round 812 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

combinatorics

constructive algorithms

dp

math

*2900

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Lost Array

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputMy orzlers, we can optimize this problem from $$$O(S^3)$$$ to $$$O\left(T^\frac{5}{9}\right)$$$!

— Spyofgame, founder of Orzlim religion

A long time ago, Spyofgame invented the famous array $$$a$$$ ($$$1$$$-indexed) of length $$$n$$$ that contains information about the world and life. After that, he decided to convert it into the matrix $$$b$$$ ($$$0$$$-indexed) of size $$$(n + 1) \times (n + 1)$$$ which contains information about the world, life and beyond.

Spyofgame converted $$$a$$$ into $$$b$$$ with the following rules.

- $$$b_{i,0} = 0$$$ if $$$0 \leq i \leq n$$$;
- $$$b_{0,i} = a_{i}$$$ if $$$1 \leq i \leq n$$$;
- $$$b_{i,j} = b_{i,j-1} \oplus b_{i-1,j}$$$ if $$$1 \leq i, j \leq n$$$.

Here $$$\oplus$$$ denotes the bitwise XOR operation.

Today, archaeologists have discovered the famous matrix $$$b$$$. However, many elements of the matrix has been lost. They only know the values of $$$b_{i,n}$$$ for $$$1 \leq i \leq n$$$ (note that these are some elements of the last column, not the last row).

The archaeologists want to know what a possible array of $$$a$$$ is. Can you help them reconstruct any array that could be $$$a$$$?

Input

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$b_{1,n}, b_{2,n}, \ldots, b_{n,n}$$$ ($$$0 \leq b_{i,n} < 2^{30}$$$).

Output

If some array $$$a$$$ is consistent with the information, print a line containing $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$. If there are multiple solutions, output any.

If such an array does not exist, output $$$-1$$$ instead.

Examples

Input

3 0 2 1

Output

1 2 3

Input

1 199633

Output

199633

Input

10 346484077 532933626 858787727 369947090 299437981 416813461 865836801 141384800 157794568 691345607

Output

725081944 922153789 481174947 427448285 516570428 509717938 855104873 280317429 281091129 1050390365

Note

If we let $$$a = [1,2,3]$$$, then $$$b$$$ will be:

$$$\bf{0}$$$ | $$$\bf{1}$$$ | $$$\bf{2}$$$ | $$$\bf{3}$$$ |

$$$\bf{0}$$$ | $$$1$$$ | $$$3$$$ | $$$0$$$ |

$$$\bf{0}$$$ | $$$1$$$ | $$$2$$$ | $$$2$$$ |

$$$\bf{0}$$$ | $$$1$$$ | $$$3$$$ | $$$1$$$ |

The values of $$$b_{1,n}, b_{2,n}, \ldots, b_{n,n}$$$ generated are $$$[0,2,1]$$$ which is consistent with what the archaeologists have discovered.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/10/2023 03:53:21 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|