NOTE: The test data for this problem are stronger than the contest version. Solutions that AC there may not get AC here.
Pusheen is playing Neko Atsume! She has a lot of toys and has laid them out to maximize her fish income. She wants to know how efficient her layout will be though.
After doing a lot of critical thinking and real-time programming, Pusheen has boiled down the fish income in terms of a single variable - the beauty of the arrangement of toys. She thus defines to be the fish income given that her layout has beauty . After some more computation, Pusheen has realized that for all , . Otherwise, .
Pusheen has layouts, layout having beauty . Compute for many values of .
The first line contains five space-separated integers, , , , , and .
The next lines each contain a single positive integer, .
Output lines, the values in order.
2 0 2 0 3 1 2 3
2 4 4