3744. 与矩阵

单点时限: 1.0 sec

内存限制: 512 MB

前有牛顿瘟疫“家里蹲”发明微积分。

现有 Cuber QQ 新冠肺炎“家里蹲”发明与矩阵。

与矩阵是一个 $n\times n$ 的矩阵。规定矩阵中的第 $i$ 行第 $j$ 列记为 $(i,j)$ 。

生成一个与矩阵的方式是,先生成一个长度为 $n$ 的数列 $a_1,a_2,\ldots, a_{n-1},a_n$ ,而矩阵中 $(i,j)=a_i\; \& \; a_j$ 。

其中 $\&$ 是指按位与运算,其计算方式是参与运算的两数各对应的二进位相与。只有对应的两个二进位都为 $1$ 时,结果位才为 $1$ 。

Cuber QQ 发现,同一个与矩阵可能对应着一些不同的数列,不过 Cuber QQ 现在只想知道字典序最小的数列是什么样的。

对于两个数列 $a_1,a_2,\ldots, a_{n-1},a_n$ 和 $b_1,b_2,\ldots, b_{n-1},b_n$ ,如果存在一个整数 $k$ ($1\le k\le n$) 满足 $a_{k+1}<b_{k+1}$ 且 $a_1=b_1,a_2=b_2,\ldots ,a_k=b_k$ ,我们就认为数列 $a_1,a_2,\ldots, a_{n-1},a_n$ 的字典序要小于数列 $b_1,b_2,\ldots, b_{n-1},b_n$ 。

当然,Cuber QQ 不会这么容易让你得到答案,他会把矩阵所有的 $(i,i)$ ($1\le i\le n$) 的位置全部隐藏,只显示为 $0$ 。

输入格式

第一行输入一个整数 $n$ ($1\le n\le 1000$) ,表示矩阵的大小。

接下来的 $n$ 行,每行 $n$ 个用空格隔开的整数 $a_{i,1},a_{i,2},\ldots ,a_{i,n}$ ($0\le a_{i,j}\le 10^7$) ,表示与矩阵。

输入保证至少存在一个可能的解。

输出格式

输出包含一行 $n$ 个用空格隔开的数,表示字典序最小的数列。

样例

Input
3
0 0 1
0 0 2
1 2 0
Output
1 2 3

提示

样例中给出的数列为 $1,2,3$ 。

451 人解决,498 人已尝试。

485 份提交通过,共有 828 份提交。

1.0 EMB 奖励。

创建: 7 月,2 周前.

修改: 7 月,2 周前.

最后提交: 2 周,1 天前.

来源: EOJ Monthly 2020.3

题目标签