该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

负责人

• CFCOI_official
• zhangruixiang
• Hamburger999
• 035966_L3

注意

本题需要使用文件读写（brooms.in / brooms.out）。

在本题中，我们定义二分图的一个完美匹配的权值为其匹配边中权值的最大值。请注意，这和通常的定义不尽相同。

题目背景

Sleeping Hippo 和他的朋友们这天上午在公园里开展了一次义务大扫除。清晨时分，他们从公园的保洁部借走了若干个扫帚。借到扫帚后，他们在公园里辛勤劳动了一上午。

现在他们已经完成了大扫除，需要去工具间归还扫帚：

• 公园里有若干个工具间。
• 将某个扫帚归还到某个工具间需要花费给定数量单位时间。
• 为了方便管理，每个工具间只能存放一把扫帚，因此任意两把扫帚都不允许归还到同一个工具间。
• 所有归还工作是同时开始的，因此总归还用时等于每把扫帚各自归还用时的最大值。
• 除了保洁部工作人员指定的若干个工具间外，其他的工具间都已经存有扫帚了 —— 这意味着每把扫帚都必须归还到上述指定的工具间之一。

Sleeping Hippo 知晓上述所有信息，除了「指定的工具间究竟有哪些」—— 这些信息需要 Sleeping Hippo 接下来向保洁部工作人员打电话确认。

假定 Sleeping Hippo 总能在确认「指定的工具间究竟有哪些」后规划并统筹执行使得总归还用时最小的方案，现在他想要解决以下问题：假设「指定的工具间的数量」已知，在序列「指定的工具间究竟有哪些」这一问题的所有可能答案中，哪种答案会使得总归还用时最大？

请对于所有「指定的工具间的数量」的可能值分别帮他解决问题。

题目描述

给定一张包含 $n$ 个左部点和 $m$ 个右部点的二分图（左部点和右部点的编号均从 $1$ 开始），其中 $i$ 号左部点和 $j$ 号右部点之间有一条权值为 $d_{i, j}$ 的边（共有 $nm$ 条边），除此以外没有其他边。你需要对 $k = n, n + 1, \ldots, m$ 分别求解以下问题：如果任意选择二分图中的 $k$ 个右部点予以保留（然后删去其他右部点以及与它们相连的边），那么操作后的二分图的最小权完美匹配的权值最大可能是多少？

输入格式

第一行两个正整数 $n, m\ (1 \le n \le 10, 1 \le m \le 10^5, n \le m)$。

下面 $n$ 行，每行 $m$ 个正整数，其中第 $i$ 行的第 $j$ 个正整数表示 $d_{i, j}\ (1 \le d_{i, j} \le nm)$。

保证矩阵 $\bm{\{d_{n, m}\}}$ 中的所有元素构成一个 $\bm{\{1, 2, \ldots, nm\}}$ 的排列。

输出格式

一行 $m - n + 1$ 个正整数，对于 $k = n, n + 1, \ldots, m$ 依次输出上述问题的答案。

样例

5 15
50 29 51 18 61 17 53 52 23 26 47 34 21 71 9
3 10 68 15 55 11 62 39 19 60 56 67 22 13 41
8 49 48 5 27 28 36 2 6 54 58 57 14 38 30
35 43 74 63 20 45 66 42 65 75 31 1 73 12 64
7 40 4 69 46 33 59 24 44 25 72 70 37 16 32

65 64 63 45 43 42 35 31 20 17 9