Õhne vanaraamatupood

Interview

Time limit1sMemory limit1023 MB

Summary

Simulate bots that repeatedly recompute their book price from the previous day's average, and print every bot's price on the morning of day T.

Level: Medium6 of 10
Topics: Implementation, Simulation, Math, Array
Solved: No attempts yet

Problem

Õhne vanaraamatupood is a startup with global reach that sells especially rare and old books online. Most of the sellers active on the portal are bots that try to buy books cheaply from one another and then resell them to other users at a higher price. Because the books are so rare, sellers even list books that they do not actually own.

Consider a particularly simple selling bot that follows the algorithm below.

If a book has never been listed for sale before, the first bot makes up an arbitrary price for it. We call this day $0$ , and this bot is numbered $1$ .
Every bot activates on a fixed schedule (once every $I$ days). When it activates, it takes the average of all offers currently on the portal (including its own offer), applies its markup (margin) $M$ to that average — that is, multiplies the average by $1 + M$ — and publishes the result as its new offer. The computation is based on the sellers' prices as they stood at the end of the previous day.

All bots that activate on the same day compute their new offers from the same snapshot, namely the prices at the end of the previous day, so updates made within a single day do not see one another.

All prices are published on the portal to the nearest cent; when a computation yields a fraction of a cent, values of $0.5$ cent or more are rounded up.

You may assume that no price ever exceeds 1,000,000.00.

Write a program that, for a single book, finds the price each bot is asking at the start of a given day. (Do not apply any price changes that would occur on that day itself.)

Input

The first line contains three numbers: the number of bots $N$ ( $1 \le N \le 100$ ), the price $P_0$ ( $0.01 \le P_0 \le 9999.99$ ) that the first bot asks for the book, and the number $T$ ( $1 \le T \le 10000$ ) of the day we are interested in.

Each of the next $N$ lines describes one bot: the day $S_i$ on which it makes its first offer ( $S_1 = 0$ ; otherwise $1 \le S_i < T$ ), the update interval $I_i$ ( $1 \le I_i \le T$ ), and the markup $M_i$ ( $0 < M_i < 1$ , given with up to 5 digits after the decimal point).

Output

Print the price each bot asks for this book on the morning of day $T$ , one per line, in the input order of the bots. Print every price with exactly two digits after the decimal point.

Examples4

Example 1

Input

3 17.99 1000
0 12 0.032
18 6 0.020
14 19 0.017

Expected output

216.27
213.75
205.07

Example 2
Input
```
1 100.00 1
0 1 0.50000
```
Expected output
```
100.00
```
Example 3
Input
```
1 10.00 5
0 1 0.10000
```
Expected output
```
14.64
```

Example 4

Input

2 50.00 30
0 5 0.05000
7 3 0.10000

Expected output

81.15
91.39