Background

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!

Problem Description

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.

Input Format

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 Format

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.

5 10
13 50 90 38 60 64 60 77 6 24

1 6
2 8
3
4 7
5 9 10

12 7
85 99 82 90 14 11 15

1
2
3
4
5
6
7
0
0
0
0
0

Hint

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