← 返回题目列表

Codeforces · 2038/H

H. 银河委员会

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

Monocarp 玩电脑游戏。在这款游戏中,他维护着一个太空帝国。帝国由$$$n$$$政党统治。最初,每个政党的政治权力都等于$$$0$$$,并且不存在执政党。

在接下来的 $$$m$$$ 回合中,会发生以下情况:

1. 最初,Monocarp 必须选择他支持的政党。他可以支持任何政党,除了执政党。当 Monocarp 支持一个政党时,其政治权力会增加 $$$1$$$。如果 Monocarp 在第 $$$j$$$ 回合中支持第 $$$i$$$ 方,他的分数会增加 $$$a_{i,j}$$$ 分;
2、然后进行选举,政治权力最大的政党被选为执政党(如果有多个这样的政党,则选择其中指数最低的政党)。前执政党被替换,除非再次选举;
3. 最后,事件发生了。在第 $$$j$$$ 回合结束时,$$$p_j$$$ 方必须是统治方,以防止事件出现不良结果,否则 Monocarp 输掉比赛。

确定Monocarp在每个回合中必须支持哪一方,这样他就不会因为事件而输掉比赛,并且他获得的分数是最大可能的。最初,Monocarp 的得分为 $$$0$$$。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n, m \le 50$$$) — 分别是政党数量和轮次数。

第二行包含 $$$m$$$ 整数 $$$p_1, p_2, \dots, p_m$$$ ($$$1 \le p_j \le n$$$),其中 $$$p_j$$$ 是第 $$$j$$$ 回合结束时应该成为执政党的政党的索引。

然后是 $$$n$$$ 行。其中第 $$$i$$$ 包含 $$$m$$$ 整数 $$$a_{i,1}, a_{i,2}, \dots, a_{i,m}$$$ ($$$1 \le a_{i,j} \le 10^5$$$),其中 $$$a_{i,j}$$$ 是 Monocarp 在支持第 $$$i$$$ 时获得的点数在第 $$$j$$$ 回合期间聚会。

输出

如果 Monocarp 输掉了比赛,无论他如何表现,都打印一个整数 $$$-1$$$。

否则,打印 $$$m$$$ 整数 $$$c_1, c_2, \dots, c_m$$$ ($$$1 \le c_j \le n$$$),其中 $$$c_j$$$ 是 Monocarp 在第 $$$j$$$ 回合中应支持的一方的索引。如果有多个答案,请打印其中任何一个。

示例

输入 #1

2 3
2 1 2
1 2 3
4 5 6

输出 #1

2 1 2

输入 #2

3 5
1 1 1 2 1
1 1 1 1 1
10 5 7 8 15
7 10 9 8 15

输出 #2

1 3 2 2 1

输入 #3

3 5
1 1 1 1 1
1 1 1 1 1
10 5 7 8 15
7 10 9 8 15

输出 #3

-1