#1721. [语言月赛 202503] 蛋挞制作工坊

[语言月赛 202503] 蛋挞制作工坊

题目描述

Alice 和 Bob 正在教小朋友们制作蛋挞。制作一个蛋挞需要 mm 种材料,编号 1∼m1 \sim m。一个蛋挞当中,材料 ii 需要 gig_i 克。

有 nn 个小朋友(编号为 1∼n1 \sim n)想要制作蛋挞,其中第 ii 个小朋友准备了 ci,jc_{i,j} 克的材料 jj。所有小朋友都用自己准备的材料制作了尽可能多的蛋挞。

现在蛋挞已经被食堂叔叔阿姨送进烤箱,小朋友们要排队领取自己的蛋挞,但是领取顺序成了一个难题。

Alice 提倡勤俭节约,所以她会指定一种材料,并让所有小朋友按照这种材料的剩余量从少到多排队,这种材料剩余量少的小朋友排在前面。

Bob 鼓励劳动,所以在 Alice 指定的材料剩余一样多时,Bob 会让制作出的蛋挞更多的小朋友排在前面;如果制作出的蛋挞也一样多,那么编号小的小朋友排前面。

你现在并不知道 Alice 指定的材料是材料 1,2,…,m1,2,\ldots,m 中的哪个,所以你想知道每一种情况下小朋友们的排队结果。

输入格式

输入共 n+2n + 2 行。

第一行两个整数 n,mn, m,代表小朋友的数量和材料的种类数。
第二行 mm 个整数 g1,⋯ ,gmg_1, \cdots, g_m,代表一个蛋挞当中每种材料需要的克数。
接下来 nn 行,每行 mm 个整数。其中第 i+2i + 2 行第 jj 列的整数为 ci,jc_{i, j},代表第 ii 个小朋友准备了 ci,jc_{i,j} 克的材料 jj。

输出格式

输出共 mm 行,每行 nn 个整数。

第 ii 行的 nn 个整数,代表 Alice 指定的材料编号为 ii 时,小朋友排队后由前到后的编号。

样例

2 2
3 5
8 14
4 9
2 1
1 2
3 2
3 5
8 14
1 4
4 9
3 2 1
1 3 2
2 3
3 5 4
6 11 8
7 10 8
1 2
2 1
1 2

题目来源:洛谷 B4250