편지 배달

UCPC 중학교에서는 다른 반 친구에게 편지를 보내는 것이 유행이다. UCPC 중학교에는 1반부터 $N$반까지 총 $N$개의 반이 있고, 각 반의 교실은 반 번호 순서대로 긴 복도를 따라 놓여 있다. $i$반 교실의 위치는 복도 시작점으로부터의 거리를 나타내는 정수 $x_i$로 표현된다.

동규는 편지 유행을 좋은 사업 기회로 보고 편지 배달 서비스를 기획했다. 학생들이 앱으로 배송 요청을 접수하면, 쉬는 시간에 편지를 일괄적으로 배달하는 서비스이다. 각 배송 요청에는 1번부터 $M$번까지 번호가 붙어 있고, 출발지와 목적지의 반 번호 쌍 $(s_i, e_i)$가 적혀 있다.

동규는 원활한 배달을 위해 각 반에서 배달원을 한 명씩 고용했다. 동규가 배달원들에게 배송 요청을 나누어 주면, 각 배달원은 받은 편지를 배달하고 동규에게 수당을 받는다. 규칙은 다음과 같다.

• 각 배달원은 동규가 정한 순서대로 편지를 배달해야 한다.
• 배달원이 편지를 둘 이상 지니면 편지가 섞일 수 있으므로, 한 번에 하나의 편지만 배달할 수 있다.
• 배달원은 배달을 모두 마치면 수업을 들어야 하므로 자기 반 교실로 돌아와야 한다.
• 각 배달원은 자기 반 교실에서 출발해 편지를 모두 배달하고 자기 반 교실로 돌아오는 데 필요한 최소 이동 거리만큼 수당을 받는다.
• 배송 요청을 배분받지 않은 배달원은 수당을 받지 않는다.

예를 들어, 4개의 교실이 간격 1로 나란히 있고, 배달할 편지의 출발지와 목적지 쌍이 순서대로 $(4,2)$, $(1,3)$이라고 하자. 1반 배달원에게 2번 편지를, 3반 배달원에게 1번 편지를 배분하면, 1반 배달원의 이동 거리는 $2+2=4$이고 3반 배달원의 이동 거리는 $1+2+1=4$이다. 따라서 동규는 두 배달원에게 총 $4+4=8$의 수당을 지급한다. (그림 I.1)

반면, 2반, 3반, 4반 배달원에게는 배분하지 않고 1반 배달원에게 2번, 1번 편지를 순서대로 배분하면, 1반 배달원의 이동 거리는 $2+1+2+1=6$이 된다. 동규는 1반 배달원에게만 $6$을 지급하면 된다. (그림 I.2)

위 예시에서는 1반 배달원에게만 2번, 1번 편지를 순서대로 배분할 때 동규가 지급할 총 수당이 최소가 된다. 배달원들에게 배송 요청을 어떻게 배분해야 하는지 구하시오.

그림 I.1: 동규가 $8$의 수당을 지급하는 배분	그림 I.2: 동규가 $6$의 수당을 지급하는 배분

첫 번째 줄에 공백으로 구분된 정수 $N$, $M$이 주어진다. ($2 \leq N \leq 300\,000$; $1 \leq M \leq 300\,000$)

두 번째 줄에 서로 다른 정수 $N$개 $x_i$가 오름차순으로 공백을 두고 주어진다. $i$번째 정수는 $i$반 교실의 위치이다. ($0 \leq x_i \leq 10^9$)

세 번째 줄부터 다음 $M$개의 줄에 공백으로 구분된 정수 $s_i$, $e_i$가 주어진다. ($1 \leq s_i, e_i \leq N$; $s_i \neq e_i$) 이 중 $i$번째 줄은 $i$번 배송 요청을 나타내며, $s_i$는 출발지 반 번호, $e_i$는 목적지 반 번호이다.

첫 번째 줄에 동규가 지급해야 하는 총 수당의 최솟값을 출력한다.

그다음 $N$개의 줄을 출력한다. 이 중 $i$번째 줄에는 $i$반 배달원에게 배분된 배송 요청의 개수를 출력한 뒤, 배달할 순서대로 배송 요청의 번호를 출력한다. 가능한 배분 방법이 여러 가지라면 그중 하나만 출력한다.