P9214 [Beginner Contest #11] Luogu Judge Simulator (Hard Version)

**This problem has exactly the same meaning as the Easy Version. The only difference is the Constraints.** Now suppose you are the Luogu judging system. On this day, Luogu is running contests such as the PION self-test, SCP self-test, and ION self-test at the same time. Tens of thousands of submissions are all coming to you!

Now it is known that you have $n$ judging nodes with identical performance, numbered $1, 2, \cdots, n$. A judging node can process only one judging task at the same time. At some moment, $m$ judging tasks arrive at the same time. We number these tasks as $1, 2, \cdots, m$. The required judging times for these tasks are $t _ 1, t _ 2, \cdots, t _ m$. Each judging task **needs exactly one** judging node to run, so you will assign these judging tasks to judging nodes one by one in order from $1$ to $m$ in the following way: For a judging task with time cost $t _ i$, you need to find the judging node that currently has the **minimum cumulative judging time** and assign the task to it. If there are multiple judging nodes whose **cumulative judging time** is the same and minimal, choose the one with the **smallest index**. > Definition of “cumulative judging time”: Suppose a judging node is assigned $k$ tasks $a _ 1, a _ 2, \cdots, a _ k$. Then the “cumulative judging time” of this judging node is $t _ {a _ 1} + t _ {a _ 2} + \cdots + t _ {a _ k}$. Obviously, if a judging node has never been assigned any of these $m$ tasks, then its “cumulative judging time” is $0$. Now you need to count which judging tasks are assigned to each of the $n$ judging nodes.

The input has two lines. The first line contains two integers $n, m$, representing the number of judging nodes and the number of judging tasks. The second line contains $m$ integers $t _ 1, t _ 2, \cdots, t _ m$, representing the required time of these $m$ judging tasks in order.

Output $n$ lines, each containing several integers separated by a single space. For the $i$-th line, output the task indices accepted by the $i$-th judging node, sorted in increasing order. If the $i$-th judging node is not assigned any task, output a single $0$ on that line.

### Constraints For $100\%$ of the testdata, it is guaranteed that $1 \leq n, m \leq 5 \times 10 ^ 5$, $0 \leq t _ i \leq 10 ^ 9$. Translated by ChatGPT 5