[Solution] Lost Array solution codeforces

Lost Array solution codeforces – A long time ago, Spyofgame invented the famous array 𝑎a (11-indexed) of length 𝑛n that contains information about the world and life. After that, he decided to convert it into the matrix 𝑏b (00-indexed) of size (𝑛+1)×(𝑛+1)(n+1)×(n+1) which contains information about the world, life and beyond.

Table of Contents

[Solution] Lost Array solution codeforces

Spyofgame converted 𝑎a into 𝑏b with the following rules.

  • 𝑏𝑖,0=0bi,0=0 if 0𝑖𝑛0≤i≤n;
  • 𝑏0,𝑖=𝑎𝑖b0,i=ai if 1𝑖𝑛1≤i≤n;
  • 𝑏𝑖,𝑗=𝑏𝑖,𝑗1𝑏𝑖1,𝑗bi,j=bi,j−1⊕bi−1,j if 1𝑖,𝑗𝑛1≤i,j≤n.

Here  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 𝑏𝑖,𝑛bi,n for 1𝑖𝑛1≤i≤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𝑛51051≤n≤5⋅105).

The second line contains 𝑛n integers 𝑏1,𝑛,𝑏2,𝑛,,𝑏𝑛,𝑛b1,n,b2,n,…,bn,n (0𝑏𝑖,𝑛<2300≤bi,n<230).

[Solution] Lost Array solution codeforces

If some array 𝑎a is consistent with the information, print a line containing 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an. If there are multiple solutions, output any.

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

Examples
input

Copy
3
0 2 1
output

Copy
1 2 3 
input

Copy
1
199633
output

Copy
199633 

[Solution] Lost Array solution codeforces

input

Copy
10
346484077 532933626 858787727 369947090 299437981 416813461 865836801 141384800 157794568 691345607
output

Copy
725081944 922153789 481174947 427448285 516570428 509717938 855104873 280317429 281091129 1050390365 
Note

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

00 11 22 33
00 11 33 00
00 11 22 22
00 11 33 11

The values of 𝑏1,𝑛,𝑏2,𝑛,,𝑏𝑛,𝑛b1,n,b2,n,…,bn,n generated are [0,2,1][0,2,1] which is consistent with what the archaeologists have discovered.

 

For Solution

Click Here

Leave a Comment