H - クッキー (Cookies) Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MiB

Score: 100 points

Problem Statement

Rie likes to make cookies. She made N types of cookies. She made A_i cookies of type i (1 \le i \le N). In order to sell the cookies made by her, she will pack them into boxes. However, the following conditions should be satisfied.

  • For every box, the types of the cookies in it should be different.
  • For every box, the number of cookies in it should be equal to one of the following M numbers: B_1, B_2, \ldots, B_M.

Write a program which, given information of cookies made by Rie and the conditions to pack the cookies into boxes, determines whether it is possible to pack all the cookies into boxes. Moreover, if it is possible to pack all the cookies into boxes, your program should output a way to pack the cookies into the minimum number of boxes.


Input

Read the following data from the standard input.

N
A_1 A_2 \cdots A_N
M
B_1 B_2 \cdots B_M

Output

If it is possible to pack all the cookies into boxes so that the conditions are satisfied, let x be the number of used boxes, c_k be the number of cookies in the k-th box (1 \le k \le x), and v_{k,1}, v_{k,2}, \ldots, v_{k,c_k} be the types of the cookies in the k-th box. Write these numbers to the standard output as in the following format.

x
c_1 v_{1,1} v_{1,2} \cdots v_{1,c_1}
c_2 v_{2,1} v_{2,2} \cdots v_{2,c_2}
\vdots
c_x v_{x,1} v_{x,2} \cdots v_{x,c_x}

Here, the number of used boxes x should be the minimum possible number. If there are several ways to pack the cookies into boxes satisfying the conditions, output any one of them.

If it is impossible to pack all the cookies into boxes so that the conditions are satisfied, write -1 to the standard output.

Constraints

  • 1 \le N \le 15\,000.
  • A_i \ge 1 (1 \le i \le N).
  • A_1 + A_2 + \cdots + A_N \le 15\,000.
  • 1 \le M \le N.
  • 1 \le B_j \le N (1 \le j \le M).
  • B_j < B_{j+1} (1 \le j \le M - 1).
  • Given values are all integers.

Subtasks

  1. (6 points) N \le 500, A_i = 1 (1 \le i \le N).
  2. (7 points) N \le 500, M = 1.
  3. (12 points) A_1 + A_2 + \cdots + A_N \le 15.
  4. (45 points) A_1 + A_2 + \cdots + A_N \le 500.
  5. (15 points) A_1 + A_2 + \cdots + A_N \le 3\,000.
  6. (15 points) No additional constraints.

Sample Input 1

7
1 1 1 1 1 1 1
3
1 2 3

Sample Output 1

3
2 1 7
2 2 6
3 3 4 5

In this sample input, it is possible to pack the 7 cookies into 3 boxes so that the conditions are satisfied as follows.

  • Pack cookies of types 1, 7 into the first box. Pack one cookie for each type.
  • Pack cookies of types 2, 6 into the second box. Pack one cookie for each type.
  • Pack cookies of types 3, 4, 5 into the third box. Pack one cookie for each type.

Your program is judged as correct if it outputs the above way to pack the cookies because it is impossible to pack the 7 cookies into less than or equal to 2 boxes so that the conditions are satisfied. There are other ways to pack the cookies which are judged as correct.

This sample input satisfies the constraints of Subtasks 1, 3, 4, 5, 6.


Sample Input 2

5
5 3 1 2 4
1
4

Sample Output 2

-1

In this sample input, it is impossible to pack the 15 cookies into boxes so that the conditions are satisfied. Therefore, output -1.

This sample input satisfies the constraints of Subtasks 2, 3, 4, 5, 6.


Sample Input 3

7
5 4 4 2 1 1 1
2
2 6

Sample Output 3

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

This sample input satisfies the constraints of Subtasks 4, 5, 6.

配点 : 100 点

問題文

クッキーを作るのが大好きな理恵さんは,N 種類のクッキーを作り,そのうち i 種類目 (1 \leqq i \leqq N) のクッキーは A_i 枚作った.理恵さんは作ったクッキーを売りたいので,以下の条件でいくつかの箱に分けて箱詰めすることにした.

  • 1 つの箱に入れるクッキーの種類は相異なる.
  • 1 つの箱に入れるクッキーの枚数は,M 種類の数 B_1, B_2, \ldots, B_M のいずれかである.

理恵さんが作ったクッキーおよび箱詰めの条件に関する情報が与えられるので,条件を満たすようにすべてのクッキーを箱詰めできるか判定し,もしできる場合は使用する箱の数が最小になるような箱詰めの方法を 1 つ求めるプログラムを作成せよ.


入力

入力は以下の形式で標準入力から与えられる.

N
A_1 A_2 \cdots A_N
M
B_1 B_2 \cdots B_M

出力

条件を満たすようにすべてのクッキーを箱詰めできる場合,使用する箱の数を x,k 番目 (1 \leqq k \leqq x) の箱に入れるクッキーの枚数を c_k,その箱に v_{k,1}, v_{k,2}, \ldots, v_{k,c_k} 種類目のクッキーを 1 枚ずつ入れるとして,標準出力に以下の形式で出力せよ.

x
c_1 v_{1,1} v_{1,2} \cdots v_{1,c_1}
c_2 v_{2,1} v_{2,2} \cdots v_{2,c_2}
\vdots
c_x v_{x,1} v_{x,2} \cdots v_{x,c_x}

ここで,使用する箱の数 x は最小でなければならない.そのような箱詰めの方法が複数ある場合は,そのうちどれを出力してもよい.

条件を満たすようにすべてのクッキーを箱詰めできない場合,標準出力に -1 を出力せよ.

制約

  • 1 \leqq N \leqq 15\,000.
  • A_i \geqq 1 (1 \leqq i \leqq N).
  • A_1 + A_2 + \cdots + A_N \leqq 15\,000.
  • 1 \leqq M \leqq N.
  • 1 \leqq B_j \leqq N (1 \leqq j \leqq M).
  • B_j < B_{j+1} (1 \leqq j \leqq M - 1).
  • 入力される値はすべて整数である.

小課題

  1. (6 点) N \leqq 500,A_i = 1 (1 \leqq i \leqq N).
  2. (7 点) N \leqq 500,M = 1.
  3. (12 点) A_1 + A_2 + \cdots + A_N \leqq 15.
  4. (45 点) A_1 + A_2 + \cdots + A_N \leqq 500.
  5. (15 点) A_1 + A_2 + \cdots + A_N \leqq 3\,000.
  6. (15 点) 追加の制約はない.

入力例 1

7
1 1 1 1 1 1 1
3
1 2 3

出力例 1

3
2 1 7
2 2 6
3 3 4 5

この入力例では,以下のような方法で,7 枚のクッキーを条件を満たすように 3 つの箱を使って箱詰めすることができる.

  • 1 番目の箱に 1, 7 種類目のクッキーを 1 枚ずつ入れる.
  • 2 番目の箱に 2, 6 種類目のクッキーを 1 枚ずつ入れる.
  • 3 番目の箱に 3, 4, 5 種類目のクッキーを 1 枚ずつ入れる.

7 枚のクッキーを条件を満たすように 2 つ以下の箱を使って箱詰めすることはできないため,この方法を出力すると正解となる.なお,この出力例の他にも正解となる出力は存在する.

この入力例は小課題 1, 3, 4, 5, 6 の制約を満たす.


入力例 2

5
5 3 1 2 4
1
4

出力例 2

-1

この入力例では,15 枚のクッキーを条件を満たすように箱詰めする方法は存在しない.したがって,-1 を出力する.

この入力例は小課題 2, 3, 4, 5, 6 の制約を満たす.


入力例 3

7
5 4 4 2 1 1 1
2
2 6

出力例 3

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

この入力例は小課題 4, 5, 6 の制約を満たす.


Source Name

JOI 2022/2023 春季トレーニング Contest Day3 問題2