codeforces#P1119G. Get Ready for the Battle

    ID: 29976 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 10 上传者: 标签>constructive algorithmsimplementation*3100

Get Ready for the Battle

Description

Recently Evlampy installed one interesting computer game, one of aspects of which is to split army into several groups and then fight with enemy's groups. Let us consider a simplified version of the battle.

In the nearest battle Evlampy should fight an enemy army that consists of mm groups, the ii-th of which has hpihp_i health points.

Evlampy's army consists of nn equal soldiers. Before each battle he should split his army in exactly mm groups (possibly, empty) so that the total size of the groups is nn. The battle is played step-by-step. On each step each of Evlampy's groups attacks exactly one enemy group. Thus, each step is described with an array of mm integers a1,a2,,ama_1, a_2, \ldots, a_m, meaning that the ii-th Evlampy's group attacks the aia_i-th enemy group. Different groups can attack same group, on each step the array aa is chosen independently.

After each step the health points of each enemy group decreases by the total number of soldiers in Evlampy's groups that attacked this enemy group at this step. Enemy group is destroyed once its health points are zero or negative. Evlampy's soldiers do not lose health.

An example of a step. The numbers in green circles represent the number of soldiers in Evlampy's groups, the arrows represent attacks, the numbers in red circles represent health points of enemy groups, the blue numbers represent how much the health points will decrease after the step.

Evlampy understands that the upcoming battle will take the whole night. He became sad because this way he won't have enough time to finish his homework. Now Evlampy wants you to write a program that will help him win in the smallest possible number of steps. Can you help him?

In other words, find the smallest number of steps needed to destroy all enemy groups and show a possible way of doing this. Find the requires splitting of the army into mm groups and the arrays aa for each step.

The first line contains two integers nn and mm (1mn1061 \leq m \leq n \leq 10^{6}) — the number of soldiers in Evlampy's army and the number of groups in enemy army. mm is also equal to the maximum possible number of groups Evlampy can split the army to.

The second line contains mm integers hp1,hp2,,hpmhp_1, hp_2, \ldots, hp_m (1hpi1061 \leq hp_i \leq 10^{6}) — the health points of each of the enemy groups.

It is guaranteed that the sum of hpihp_i does not exceed 10610^{6}.

Print a single integer tt — the minimum possible number of steps needed to win the battle.

After that print mm integers s1,s2,,sms_1, s_2, \ldots, s_m (si0s_i \ge 0, s1+s2++sm=ns_1 + s_2 + \ldots + s_m = n), meaning that the ii-th group of Evlampy's army should contain sis_i soldiers.

In each of the next tt lines print mm integers a1,a2,,ama_1, a_2, \ldots, a_m (1aim1 \le a_i \le m) — the description of one step. The integers mean that on the corresponding step the ii-th Evlampy's group should attack the aia_i-th enemy group. It is allowed to attack an already destroyed group.

Input

The first line contains two integers nn and mm (1mn1061 \leq m \leq n \leq 10^{6}) — the number of soldiers in Evlampy's army and the number of groups in enemy army. mm is also equal to the maximum possible number of groups Evlampy can split the army to.

The second line contains mm integers hp1,hp2,,hpmhp_1, hp_2, \ldots, hp_m (1hpi1061 \leq hp_i \leq 10^{6}) — the health points of each of the enemy groups.

It is guaranteed that the sum of hpihp_i does not exceed 10610^{6}.

Output

Print a single integer tt — the minimum possible number of steps needed to win the battle.

After that print mm integers s1,s2,,sms_1, s_2, \ldots, s_m (si0s_i \ge 0, s1+s2++sm=ns_1 + s_2 + \ldots + s_m = n), meaning that the ii-th group of Evlampy's army should contain sis_i soldiers.

In each of the next tt lines print mm integers a1,a2,,ama_1, a_2, \ldots, a_m (1aim1 \le a_i \le m) — the description of one step. The integers mean that on the corresponding step the ii-th Evlampy's group should attack the aia_i-th enemy group. It is allowed to attack an already destroyed group.

Samples

输入数据 1

13 7
6 4 3 7 2 1 5

输出数据 1

3
0 1 2 3 1 2 4
2 6 2 4 4 2 4
3 1 7 1 7 7 1
3 1 5 3 7 5 1

输入数据 2

6 5
3 3 3 3 3

输出数据 2

3
3 3 0 0 0
1 2 3 4 5
3 4 5 5 5
5 5 5 5 5

输入数据 3

7 4
1 5 9 2

输出数据 3

3
1 2 4 0
1 4 2 3
2 3 3 3
3 3 3 3

Note

The first example is shown below.