题目描述

在 UCPC 中学，给其他班级的朋友寄信非常流行。

学校共有 $N$ 个班级，编号为 $1$ 到 $N$。各班教室沿一条很长的走廊按班级编号顺序排列。第 $i$ 个班级教室的位置用整数 $x_i$ 表示，即它到走廊起点的距离。

东奎认为这是一个很好的商机，于是设计了一项统一送信服务。学生通过应用提交送信请求，所有信件会在课间集中配送。

共有 $M$ 个送信请求，编号为 $1$ 到 $M$。第 $i$ 个请求由一对班级编号 $(s_i,e_i)$ 表示：信件需要从班级 $s_i$ 送往班级 $e_i$。

为了完成配送，东奎从每个班级雇用了一名配送员。东奎需要把所有送信请求分配给这些配送员，并为每名配送员指定处理请求的顺序。规则如下：

• 每名配送员必须按照东奎指定的顺序配送信件；
• 为避免信件混淆，配送员一次最多携带一封信；
• 配送员从自己班级的教室出发；
• 完成分配给自己的全部配送任务后，配送员必须返回自己的班级上课；
• 每名配送员获得的报酬，等于他从自己的教室出发、按指定顺序完成所有任务并返回教室所需的最短总移动距离；
• 没有被分配任务的配送员不获得报酬。

例如，假设有 $4$ 个班级，教室之间的间距均为 $1$，两个请求依次为 $(4,2)$ 和 $(1,3)$。

若把第 2 个请求交给 1 班配送员，把第 1 个请求交给 3 班配送员，则两人的移动距离分别为 $4$ 和 $4$，总报酬为 $8$。

图 I.1：总报酬为 8 的分配方式

若把两个请求都交给 1 班配送员，并按第 2、1 个请求的顺序配送，则总移动距离为 $6$。

图 I.2：总报酬为 6 的分配方式

在这个例子中，后者是最优方案。

请找出一种使所有配送员总报酬最小的任务分配与配送顺序。

输入格式

第一行包含两个整数 $N,M$。

第二行包含 $N$ 个严格递增的整数 $x_1,x_2,\ldots,x_N$，其中 $x_i$ 表示第 $i$ 个班级教室的位置。

接下来 $M$ 行描述送信请求。第 $i$ 行包含两个整数 $s_i,e_i$，表示第 $i$ 个请求需要把信件从班级 $s_i$ 送到班级 $e_i$。

输出格式

第一行输出东奎需要支付的最小总报酬。

接下来输出 $N$ 行。第 $i$ 行描述 $i$ 班配送员的任务：

• 先输出分配给该配送员的请求数量 $k_i$；
• 再按实际配送顺序输出这 $k_i$ 个请求的编号。

若某名配送员没有任务，只输出 0。

若存在多种最优方案，输出任意一种即可。

数据范围

• $2\le N\le 300\,000$；
• $1\le M\le 300\,000$；
• $0\le x_i\le 10^9$，且所有 $x_i$ 两两不同并严格递增；
• $1\le s_i,e_i\le N$；
• $s_i\ne e_i$。

样例

输入

4 2
1 2 3 4
4 2
1 3

输出

6
2 2 1
0
0
0