[Solution] Lost Array Codeforces Solution

F. Lost Array

time limit per test

1 second

memory limit per test

25

time ago, Spyofgame invented the famous array 

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

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

• bi,0=0$b_{i,0}=0$ if 0≤i≤n$0\le i\le n$;
• b0,i=ai$b_{0,i}=a_i$ if 1≤i≤n$1\le i\le n$;
• bi,j=bi,j−1⊕bi−1,j$b_{i,j}=b_{i,j-1}\oplus b_{i-1,j}$ if 1≤i,j≤n$1\le i,j\le n$.

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

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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 occupied

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

Input

The first line contains a single integer n$n$ (1≤n≤5⋅105$1\le n\le 5\cdot {10}^5$).

The second line contains n$n$ integers b1,n,b2,n,…,bn,n$b_{1,n},b_{2,n},\dots ,b_{n,n}$ (0≤bi,n<230$0\le b_{i,n}<2^{30}$).

Output

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

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