Problem N
Perfect Skyline

Source: pixabay

Zara, an aspiring architect and urban planner, has drawn out what she considers to be the perfect skyline. As Zara is still aspiring she must use her young daughter, Pippa, to test out her designs. In order to test out the designs Pippa must build them out of her building blocks! The building blocks Pippa has have a uniform width and depth, but come in different heights $h$. Zara’s description for Pippa will consist of a list of buildings, each with a target height $b$.

Pippa must then use some (not necessarily all) of her blocks to stack together such that the sum of the heights of the blocks in each stack corresponds to the height of the building in the skyline. Since Pippa prefers building instead of solving puzzles she wants you to determine how she must stack the blocks so that she must only do the stacking!


The input consists of a single test case. The first line of this test case contains two integers $N$ and $S$ ($1 \le N \le 15$ and $1 \le S \le 15$), where $N$ is the number of blocks Pippa has and $S$ is the number of buildings in the skyline Zara made.

The next line contains $N$ integers ($1 \le h_ i \le 10^{9}$) representing the heights of each of the blocks. The last line contains $S$ integers ($1 \le b_ i \le 10^{9}$) representing the heights of each of the buildings.


If it is possible for Pippa to build Zara’s skyline then output $S$ lines. On each line output a single number $s_ i$ representing the number of blocks needed to build building $i$ where $i$ corresponds to the $i^{\text {th}}$ building listed in the input. This should be followed (on the same line) by $s_ i$ numbers $j$ representing the blocks of the input used in building $i$, where $j$ represents the $j^{\text {th}}$ block appearing the input.

If no combination of the blocks can build the desired skyline then output -1.

Sample Input 1 Sample Output 1
4 3
3 3 2 1
3 3 3
1 1
1 2
2 3 4
Sample Input 2 Sample Output 2
4 2
3 3 2 2
6 3
Sample Input 3 Sample Output 3
7 3
5 4 3 6 1 2 2
4 11 4
1 2
2 1 4
2 3 5

Please log in to submit a solution to this problem

Log in