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
.
Constraints
Input Specification
The first line contains five space-separated integers, ,
,
,
, and
.
The next lines each contain a single positive integer,
.
Output Specification
Output lines, the
values in order.
Sample Input
2 0 2 0 3
1
2
3
Sample Output
2
4
4
Comments