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