Letter Delivery

UCPC Middle School has a trend of sending letters to friends in other classes. The school has $N$ classes, numbered $1$ through $N$, and each classroom lies along a long corridor in class number order. The position of the classroom for class $i$ is the integer $x_i$, the distance from the start of the corridor.

Donggyu saw the letter trend as a good business opportunity and planned a letter delivery service. Students submit delivery requests through an app, and the letters are delivered in bulk during break time. Each request is numbered from $1$ to $M$ and lists a pair $(s_i, e_i)$ of class numbers for its origin and destination.

For smooth delivery, Donggyu hired one courier from each class. He assigns the requests to the couriers, and each courier delivers the assigned letters and is paid by Donggyu. The rules are as follows.

• Each courier must deliver letters in the order Donggyu sets.
• If a courier carries two or more letters, the letters may get mixed up, so a courier delivers only one letter at a time.
• After finishing all deliveries, a courier must return to their own classroom to attend class.
• Each courier starts at their own classroom, delivers all assigned letters, and returns to their own classroom. The courier is paid the minimum travel distance needed for this.
• A courier who is not assigned any request is not paid.

For example, suppose four classrooms sit in a row with a gap of $1$ between neighbors, and the requests have origin and destination pairs $(4,2)$ and $(1,3)$, in that order. If the class 1 courier gets request 2 and the class 3 courier gets request 1, the class 1 courier travels $2+2=4$ and the class 3 courier travels $1+2+1=4$. Donggyu pays $4+4=8$ in total to the two couriers. (Figure I.1)

If no request goes to the couriers of classes 2, 3, and 4, and the class 1 courier delivers request 2 and then request 1, the class 1 courier travels $2+1+2+1=6$. Donggyu pays only $6$, to the class 1 courier. (Figure I.2)

In this example, giving requests 2 and 1 in order to the class 1 courier alone gives the lowest total pay. Determine how Donggyu should assign the requests to the couriers.

Figure I.1: An assignment where Donggyu pays $8$	Figure I.2: An assignment where Donggyu pays $6$

The first line contains two integers $N$ and $M$, separated by a space. ($2 \leq N \leq 300\,000$; $1 \leq M \leq 300\,000$)

The second line contains $N$ distinct integers $x_i$ in increasing order, separated by spaces. The $i$-th integer is the position of the classroom of class $i$. ($0 \leq x_i \leq 10^9$)

Each of the next $M$ lines contains two integers $s_i$ and $e_i$, separated by a space. ($1 \leq s_i, e_i \leq N$; $s_i \neq e_i$) The $i$-th of these lines describes request $i$, where $s_i$ is the origin class number and $e_i$ is the destination class number.

On the first line, print the minimum total pay Donggyu must give to the couriers.

Then print $N$ lines. On the $i$-th line, print the number of requests assigned to the courier of class $i$, followed by the request numbers in the order they are delivered. If more than one assignment is possible, print only one of them.