Background

Special for beginners, ^_^

Description

新疆的某个矿场里新出了一批和田玉的籽料，大大小小共有n块，每一块和田玉都有各不相同的价值ai。 现需将这批和田玉籽料装入m只箱子中运到玉交易市场。

为了让这m只箱子的价值差之和最小，工人们对着n块玉按照价值大小依次排序，惊奇的发现这些玉每一块的价值与相邻的玉的差值竟然也各不相同。

箱子的价值差是指：箱子中一共有t块玉，每块玉的价值从大到小依次为A1，A2……，At，那么这只箱子的价值差值为：(A1-A2+A2-A3+……+At-1-At)；如果箱子中只有1块玉，那么箱子的价值差就为0。

而m只箱子总体的价值差，就是各个箱子价值差的和。

现在要把这n块玉装入到m只箱子中了，尽量让编号小的玉放在编号小的箱子，请你替工人规划一下该如何装箱才能使得m只箱子的价值差最小。

输出时分别输出1号箱子到m号箱子内该装的玉，每只箱子中的玉按价值从小到大的顺序输出。

Format

Input

第1行两个正整数n和m $(m\le n\le10^6)$，分别表示玉的数量和箱子的数量；

第2行n个整数 $a_i\le10^9$，分别表示每块玉的价值。

Output

m行数，每行数字的开头是一个箱子的编号及冒号（英文输入下的冒号），后面若干个用1个空格隔开的整数，表示装入这个箱子的玉的价值。

Samples

4 3
24 37 38 40

1:24
2:37 38
3:40

Limitation

1s, 1024KiB for each test case.