← 返回题目列表

Codeforces · 245/D

D. 恢复表

中文机器翻译题面 查看原题

最近Polycarpus学会了非负整数的“按位与”运算(也称为“AND”)。现在他想用学到的操作向学校IT老师展示他高超的操作能力。

因此,Polycarpus 早一点到了学校,并在黑板上写下了一系列非负整数 a1, a2, ..., an。他还写了一个大小为 n × n 的方阵 b。矩阵 b 中第 i 行第 j 列的元素(我们将其表示为 bij)等于:

- 数字 ai 和 aj 的“按位与”(即 bij = ai & aj),如果 i ≠ j;
- -1,如果 i = j。

写出矩阵b后,Polycarpus很高兴,把a从黑板上擦掉了。但问题是,老师会想要这个序列来检查波利卡普斯的计算是否正确。波利卡洛斯迫切需要恢复被删除的整数序列,否则他将无法证明自己能够正确计数。

帮助 Polycarpus,给定矩阵 b,恢复他从棋盘上删除的数字 a1, a2, ..., an 的序列。 Polycarpus 不喜欢大数字,因此恢复序列中的任何数字都不得超过 109。

输入

第一行包含一个整数 n (1 ≤ n ≤ 100) — 方阵 b 的大小。接下来的 n 行包含矩阵 b。这些行的第 i 行包含 n 个空格分隔的整数:第 j 个数字表示矩阵 bij 的元素。保证对于所有 i (1 ≤ i ≤ n) 满足以下条件:bii = -1。保证对于所有 i, j (1 ≤ i, j ≤ n; i ≠ j) 满足以下条件:0 ≤ bij ≤ 109,bij = bji。

输出

打印 n 个非负整数 a1, a2, ..., an (0 ≤ ai ≤ 109) — Polycarpus 从棋盘上擦掉的序列。用空格分隔数字。

保证存在满足问题条件的序列a。如果有多个这样的序列,您可以打印其中任何一个。

示例

输入 #1

1
-1

输出 #1

0

输入 #2

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

输出 #2

18 18 0

输入 #3

4
-1 128 128 128
128 -1 148 160
128 148 -1 128
128 160 128 -1

输出 #3

128 180 148 160

注意

如果您不知道什么是“按位与”运算,请阅读:http://en.wikipedia.org/wiki/Bitwise_operation。