Balance#3137

Balance

3 seconds

64 megabytes

Very hard

An investor invests a certain percentage of their assets into $NINSTRUMENTS$ financial instruments. At the end of each term, these instruments deduct a fixed administrative fee, then a fee that is a percentage of the amount invested at the beginning of the term, and then apply a return, which may be a positive or negative percentage of the amount invested at the beginning of the term. If any account becomes zero or below after such a transaction, it is considered closed (no fees are charged and it is treated as zero) until the next rebalancing occurs. Rebalancing takes place every $NREBALANCE$ terms, at which point the investor's total assets are redistributed among the instruments in the original proportions. Without rebalancing, the investor's assets may become dominated by higher return instruments, increasing risk compared to a balanced investment plan. Note that all instruments may reach zero, in which case they remain closed for the remaining terms. You are to simulate the value of such an investment strategy and report the final amount in each instrument (before rebalancing, if it falls on a rebalance term). Compute your results using double precision (do not round intermediate values to pennies), but round your final answers to pennies.

Input

The first line contains three positive integers: $NINSTRUMENTS$ , $NTERMS$ , $NREBALANCE$ . There are no more than $10$ instruments, and the number of terms is at most $20$ . The next $3$ lines contain floating-point numbers separated by spaces, as follows:

$FIXED_FEE (1) \dots FIXED_FEE (NINSTRUMENTS)$ \mathrm{FIXED\_FEE}(1) \ldots \mathrm{FIXED\_FEE}(\mathrm{NINSTRUMENTS}) $PERCENTAGE_FEE (1) \dots PERCENTAGE_FEE (NINSTRUMENTS)$ \mathrm{PERCENTAGE\_FEE}(1) \ldots \mathrm{PERCENTAGE\_FEE}(\mathrm{NINSTRUMENTS}) $PRINCIPAL_START (1) \dots PRINCIPAL_START (NINSTRUMENTS)$ \mathrm{PRINCIPAL\_START}(1) \ldots \mathrm{PRINCIPAL\_START}(\mathrm{NINSTRUMENTS})

Finally, there are $NTERMS$ lines, each containing $NINSTRUMENTS$ floating-point numbers indicating the percentage return for each instrument in each term:

$RETURN (1, 1) \dots RETURN (1, NINSTRUMENTS)$ \mathrm{RETURN}(1,1) \ldots \mathrm{RETURN}(1,\mathrm{NINSTRUMENTS}) $RETURN (2, 1) \dots RETURN (2, NINSTRUMENTS)$ \mathrm{RETURN}(2,1) \ldots \mathrm{RETURN}(2,\mathrm{NINSTRUMENTS}) $\dots$ $RETURN (NTERMS, 1) \dots RETURN (NTERMS, NINSTRUMENTS)$ \mathrm{RETURN}(\mathrm{NTERMS},1) \ldots \mathrm{RETURN}(\mathrm{NTERMS},\mathrm{NINSTRUMENTS})

All percentages (that is, $PERCENTAGE_FEE$ and $RETURN$ ) are given as ratios, up to $4$ decimal places. For example, a fee of $0.0002$ means $0.02%$ of the investment in this instrument is deducted each term. $FIXED_FEE$ and $PRINCIPAL_START$ are non-negative floating-point numbers given with up to $2$ decimal places. At least one $PRINCIPAL_START$ value is positive.

Output

Print in one line the principal amount of each investment (separated by spaces) at the end of $NTERMS$ terms. Round each principal to the nearest penny.

$PRINCIPAL_END (1) \dots PRINCIPAL_END (NINSTRUMENTS)$ \mathrm{PRINCIPAL\_END}(1) \ldots \mathrm{PRINCIPAL\_END}(\mathrm{NINSTRUMENTS})

Examples

Example 1