Dino loves ice cream. In case he ever run out of ice cream at his office, he keeps a stash of dry ice in order to quickly make new ice cream.
His recipe for making ice cream includes exactly $T$ liters of dry ice. Unfortunately, he has no marked containers in his office. Instead, he keeps a set of bottles of known total volume.
He wants to use this in order to transfer $T$ liters of dry ice from his dry ice container to the container in which he is mixing his ice cream. To do this, he should perform a sequence of three different kinds of actions. He may either fill a bottle with dry ice from the dry ice container until the bottle is full, empty the contents of a bottle into the ice container, or transfer dry ice from one bottle into other until either the first bottle becomes empty or the target bottle becomes full.
Can you help Dino construct a plan in order to transfer $T$ liters of dry ice into the ice cream mix?
The first line of the input contains an integer $1 \le N \le 100$, the number of bottles.
The next line contains $N$ integers, separated by spaces. These are the volumes of all the bottles, in liters. Each volume is between $1$ and $100$ liters.
The final line contains the integer $1 \le T \le 100$, the volume in liters of dry ice needed for the ice cream.
If it is not possible to add the correct amount of dry ice, output impossible. Otherwise, output a sequence of moves that moves $T$ liters into the ice cream mix.
You may output the following moves:
fill x: Fill bottle $x$ from the ice cream container until it is full.
discard x: Empty bottle $x$ into the sink.
transfer x y: Pour from bottle $x$ into bottle $y$ until either $y$ is full or $x$ is empty.
When pouring dry ice into the ice cream mix, use $y = 0$ as the target bottle.
You may output at most $100\, 000$ moves.
Sample Input 1 | Sample Output 1 |
---|---|
2 7 8 10 |
fill 2 transfer 2 1 transfer 2 0 discard 1 fill 2 transfer 2 1 transfer 2 0 discard 1 fill 2 transfer 2 0 |
Sample Input 2 | Sample Output 2 |
---|---|
2 2 4 3 |
impossible |