Identifying Malfunctioning QC Machines

Innovative Computable Quality Control (ICQC) has developed a revolutionary QC machine using Deep Intelligence technology, with which it can detect manufacturing errors (with 100% accuracy) in any machine – from coffee machines and intergalactic space ships to quantum computers. However, when producing these QC machines in batches, some machines may be malfunctioning. Since a malfunctioning machine might give a false report about itself when tested, ICQC has designed a scheme in which each machine is tested by every other machine over several rounds.

In each batch of n machines, every machine tests every other machine exactly once (the result is the same in every round if repeated). If the machine doing the testing is working correctly then it will report the true status of the tested machine (1 if working, 0 if malfunctioning); if it is malfunctioning then it may report arbitrarily. Moreover, ICQC is 100% certain that more than half of the machines in every batch are working correctly. This guarantees that the majority of reports about any machine come from machines who reliably tell the truth.

Your task is to help ICQC decide which machines are malfunctioning. You are given an n × n matrix of test results. In this matrix, the entry in row i and column j represents the result reported by machine i when it tested machine j. (Note that a machine does not test itself; its corresponding entry can be ignored.)

Since every working machine always tells the truth, for any machine j the votes from all the working machines will be consistent. In particular, if machine j is working then each working machine will report 1 when testing it; if machine j is malfunctioning then every working machine will report 0 when testing it. Even though the malfunctioning machines can give arbitrary responses, they cannot outvote the majority of correct machines. Therefore, for each machine j if at least ⌊n/2⌋ of the other machines claim that it is working (i.e. return 1), then it is safe to assume that machine j is working; otherwise, it is malfunctioning.

Note: Here, ⌊n/2⌋ denotes the floor of n/2. For example, if n = 4, each machine is tested by 3 other machines. If at least 2 of these tests report a result of 1, then the machine is classified as working; otherwise, it is classified as malfunctioning.

Design an algorithm to output the status of each machine in the batch.

inputFormat

The first line contains a single integer n (n ≥ 3), the number of machines in the batch. The next n lines each contain n space‐separated integers. The integer in the i-th row and j-th column indicates the result reported by machine i when testing machine j (either 0 or 1). You should ignore the entries where i = j since no machine tests itself.

outputFormat

Output a single line containing n integers separated by spaces. The j-th integer should be 1 if machine j is working correctly, or 0 if it is malfunctioning.

Note: A machine is considered working if at least ⌊n/2⌋ of the other machines reported that it is working.

sample

3
-1 1 1
0 -1 0
0 1 -1

1 1 0