Problem Description

After overcoming many difficulties, you have infiltrated the Death Star. To destroy it, you need an array $a$ of length $n$ to start the Death Star’s self-destruction command. Although you do not know what this array is, your old friend Darth Vader gave you an $n \times n$ matrix $b$ in advance. In this matrix, the element in row $i$ and column $j$ satisfies $b_{i,j}=a_i\operatorname{~and~} a_j$, where $\operatorname{and}$ means the bitwise AND operation. Just when you thought you could directly obtain the array $a$ from this matrix, you found that all elements on the main diagonal were destroyed by a lightsaber. You cannot read their values, so they are temporarily replaced with $0$.

Now, based on the other undamaged elements, find any array $a$ that satisfies the requirements.

Input Format

The first line contains an integer $n$, the order of the matrix $b$.
Then follow $n$ lines, each containing $n$ integers describing the matrix $b$.

Output Format

Output one line with $n$ integers, representing an array $a$ that satisfies the conditions. Each element of the array must be a non-negative integer not exceeding $10^9$.

The testdata guarantees that a solution exists, but it is not guaranteed to be unique.

3
0 1 1
1 0 1
1 1 0

1 1 1

5
0 0 1 1 1
0 0 2 0 2
1 2 0 1 3
1 0 1 0 1
1 2 3 1 0

1 2 3 1 11

Hint

[Sample 1 Explanation]

It is easy to see that one valid array is $a=[1,1,1]$, but please note that this is not the only possible answer.

[Constraints]

For all testdata, $1\leqslant n\leqslant 1000$, $0\leqslant b_{i,j}\leqslant 10^9$.

This problem uses Special Judge. If you have testdata that can hack the checker written by the problem setter, or if you have suggestions to improve the checker, feel free to post them in the discussion area below this problem.

[Source]

This problem is from COCI 2015-2016 CONTEST 4 T3 DEATHSTAR, using the original test configuration, with a full score of $100$ points.

Translated and organized by Eason_AC.

Translated by ChatGPT 5