[入门赛 #11] 洛谷评测机模拟器 (Hard Version)

现在已经知道你有 $n$ 个相同性能的评测节点，它们被分别标号为 $1, 2, \cdots, n$。一个评测节点在同一时间只能处理一个评测任务。 在某一时刻，$m$ 个评测任务同时涌入了你。我们将这些任务分别标号为 $1, 2, \cdots, m$。这些评测任务需要的评测时间分别为 $t _ 1 , t _ 2, \cdots, t _ m$。每个评测任务**需要且仅需要一个**评测节点来运行，因此你会按照如下方式按照 $1 \sim m$ 的顺序依次将这些评测任务分配到评测节点上： 对于某个耗时 $t _ i$ 的评测任务，你需要找到目前**累积评测时间**最小的评测节点将任务放入。如果有多个评测节点**累积评测时间**相同且最小，则找一个**标号最小**的节点将任务放入。 > 「累积评测时间」定义：假设对于某个评测节点，其被分配了 $a _ 1, a _ 2, \cdots, a _ k$ 共 $k$ 个任务。那么这个评测节点的「累积评测时间」就是 $t _ {a _ 1} + t _ {a _ 2} + \cdots + t _ {a _ k}$。显然的，如果某个评测节点从未被分配过这 $m$ 个任务中的任何一个，那么这个评测节点的「累积评测时间」是 $0$。 现在，你需要统计出，你的这 $n$ 个评测节点分别接受了哪一些评测任务。 ## Input 输入共两行。 第一行为两个整数 $n, m$，代表评测节点数量和评测任务数量。 第二行为 $m$ 个整数 $t _ 1, t _ 2, \cdots, t _ m$，依次代表这 $m$ 个评测任务的所需时间。 ## Output 输出共 $n$ 行，每行若干个整数，两两之间以一个空格隔开。 对于第 $i$ 行，输出第 $i$ 个评测节点接受的评测任务编号从小到大排序后的结果。如果第 $i$ 个评测节点没有被分配任务，那么输出一行一个 $0$。 [samples] ## Background **本题与 Easy Version 题意完全相同，不同的地方在于数据范围。** 现在假装你是洛谷评测机。这一天，洛谷同时进行了 PION 自测、SCP 自测、ION 自测等等比赛。成千上万的评测落到了你的身上！ ## Note ### 数据规模与约定 对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 5 \times 10 ^ 5$，$0 \leq t _ i \leq 10 ^ 9$。