Description

在长城附近有一个停车中心,车辆只能从左到右沿一条长队停放。现在,该停车场 内已经停满车辆,每一辆车有品牌之别,可能有多辆车是同一品牌的。车辆的品牌由整 数表示。若干工人正在设法将车辆按照品牌重新排序,使得它们按品牌编号从左到右递 增排列。但是,调度是按照轮次进行的。每一轮调度中,每个工人只能将一辆车开出车 队以腾出一个空位,然后将该车插入在当前轮中其他工人腾出的空位。当然,有的工人 在某些轮次中可能不用移动车辆。为了提高效率,需要用尽可能少的轮次完成调度。

假设现有 N 辆车和 W 个工人。请你编写一个程序,对给定的 N 和 W,在不超过 「N/(W-1)]轮内完成对车辆的排序。这里,「N/(W-1)]表示不小于 N/(W-1)的最小整数。 在任何情况下,需要调度的最少轮数总不会超过「N/(W-1)]。

下面是一个例子:停车场中共有 4 种品牌的 10 辆车,4 种品牌用整数 1 、 2 、 3 和 4 表示:共有 4 名工人。在初始时刻,从左到右车辆的品牌编号依次为:

2 3 3 4 4 2 1 1 3 1

这个例子需要的最少调度轮次为 3 ,每一轮调度后的结果分别是:

2 1 1 4 4 2 3 3 3 1

2 1 1 2 4 3 3 3 4 1

1 1 1 2 2 3 3 3 4 4

 第 1 轮后,

 第 2 轮后,以及

 第3 轮后。

Format

Input

输入文件名为 CAR.IN。

第一行包括 3 个整数:

n第一个整数是车辆数 N ,2≤ N≤20000;

0第二个整数是车辆的品牌数 M ,2≤ M≤50,车辆的品牌用 1 到 M 的整数表示:

o第三个整数是工人数 W ,2≤W ≤ M。

第二行有 N 个整数,其中第 i 个整数表示从左数起第i 辆车的品牌。

Output

输出文件名为 CAR.OUT。

第一行只有一个整数 R ,表示你求出的最少轮次数。

接下来的 R 行依次描述从第 1 到第 R 轮的调度方案。

在每一行中,第一个整数 C 表示该轮中需要移动的车辆总数。其后是 2C 个整数, 表示车辆的位置。车辆的位置从左到右用 1 到 N 的整数依次编号。这 2C 个整数中的前 两个描述了一辆车的移动方案:前者是该车在该轮移动前的位置,后者是移动后的位

置。接下来的两个整数描述另一辆车的移动方案,依此类推。

这 R 行可能有多种不同形式,你只需输出其中一种。

Samples

10 4 4
2 3 3 4 4 2 1 1 3 1

3
4 2 7 3 8 7 2 8 3
3 4 9 9 6 6 4
3 1 5 5 10 10 1

Limitation

假设基准调度轮次 Q=「N/(W-1)],你得到的结果为 R。

如果程序的输出不能正确描述一个调度过程,或者调度结果没有达到排序要求,你 的得分为 0。

否则,你的得分将按下面规则计算:

9 R≤Q 100%的分

9 R=Q+1 50%的分

9 R=Q+2 20%的分

9 R≥Q+3 0%的分