← 返回题目列表

Codeforces · 1492/E

E. 几乎容错的数据库

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

您正在数据库中存储长度为 $$$m$$$ 的整数数组。为了维护内部完整性并保护数据,数据库存储该数组的 $$$n$$$ 副本。

不幸的是,最近的事件可能改变了数据库中每个副本中存储的信息。

据信,该事件最多改变了每个副本中的两个元素。您需要根据数据库的当前状态恢复原始数组。

如果有多种方法可以恢复阵列,请报告任何一种。如果没有数组与每个副本的差异不超过两个位置,也报告这一点。

输入

第一行包含整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n$$$; $$$1 \le m$$$; $$$n \cdot m \le 250\,000$$$) — 副本数和数组大小。

下面的每一行 $$$n$$$ 描述数据库中当前存储的副本之一,它由 $$$m$$$ 整数 $$$s_{i, 1}, s_{i, 2}, \dots, s_{i, m}$$$ ($$$1 \le s_{i, j} \le 10^9$$$) 组成。

输出

如果存在与所有给定副本一致的数组,则打印“Yes”,然后打印数组本身。该数组的长度必须为 $$$m$$$,并且仅包含 $$$1$$$ 和 $$$10^9$$$ 之间的整数。

否则,打印“否”。

如果有多个可能的数组,则打印其中的任何一个。

示例

输入 #1

3 4
1 10 10 100
1 1 1 100
10 100 1 100

输出 #1

Yes
1 10 1 100

输入 #2

10 7
1 1 1 1 1 1 1
1 1 1 1 1 1 2
1 1 1 1 1 2 2
1 1 1 1 2 2 1
1 1 1 2 2 1 1
1 1 2 2 1 1 1
1 2 2 1 1 1 1
2 2 1 1 1 1 1
2 1 1 1 1 1 1
1 1 1 1 1 1 1

输出 #2

Yes
1 1 1 1 1 1 1

输入 #3

2 5
2 2 1 1 1
1 1 2 2 2

输出 #3

No

注意

在第一个示例中,数组 $$$[1, 10, 1, 100]$$$ 与第一个和第二个副本仅在一个位置不同,与第三个副本在两个位置不同。

在第二个示例中,数组 $$$[1, 1, 1, 1, 1, 1, 1]$$$ 与第一个副本相同,但最多有两个位置与所有其他副本不同。

在第三个示例中,每个数据库副本中不存在最多两个位置不同的数组。