Chemical mixture

4

46 votes
Easy-Medium, Greedy algorithm
Problem

View Russian Translation

A wild chemist wants to prepare his mysterious mixture.

The recipe is very simple, he has already mixed all the necessary powders and the only remaining thing is to add exactly m nanoliters of any liquids.

In his lab he has n1 bottles full of liquid called amulus of various capacities and n2 bottles full of water, also of various capacities. He knows the capacity of each single bottle and he is curious if he can use the bottles he has to produce the mixture. If he decides to use any bottle, he has to use all the liquid inside it.

Capacities of bottles of amulus are special, because for any two such bottles with capacities ci and cj, the following fact is true:

either 2cicj or 2cjci.

Help the chemist decide if he can prepare the mixture or not.

In one test file you have to handle T test cases.

Input format:

In the first line a single integer T is given denoting the number of test cases. Then descriptions of T test cases follow. In the first line of a description of a single test case there are three integers m, n1 and n2 ,denoting the number of nanoliliters of liquids needed for the mixture, the number of bottles of amulus available and the number of bottles of water available. In the second line there are n1 space separated integers denoting capacities of bottles of amulus. In the third line there are n2 integers denoting capacities of bottles of water.

Output format:

For each test case output either NO if the mixture cannot be produced, or output YES in the first line followed by the second line containing space separated capacities of bottles of amulus that can be used to achieve the goal in non-decreasing order of their capacities. If there are many possible solutions output the one with the greatest sum of capacities of used bottles of amulus, and in case when there are still many possible such solutions, print any of them.

Constraints:

1T10
1m1018
1n160
1n215
1 capacity of any bottle 1017
For any two bottles of amulus with capacities c1 and c2, either 2cicj or 2cjci

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

There are two test cases in the sample. In both of them we have there are two bottles of amulus with capacities 2 and 4, and two bottles of water with capacities 1 and 3.

In the first test case a mixture of 7 nanoliters can be mixed using both bottles of amulus and a bottle of water with capacity 1. There are other possible solutions, but this one is the one with greatest sum of nanoliters of amulus used among them.

In the second test case there is no possible combination of bottles giving 11 nanoliters of mixture.

Editor Image

?