Production Waste
本题没有可用的提交语言。
Description
A large industrial company manages a plant that produces important goods and ecologically disposes of waste. Even on days when the plants are idle (which can happen frequently) a portion of the waste is still disposed of safely.
It is known that the plants operated for $n$ days, and the $i$-th day was the $d_i$-th production day since the company started operating. On this day, $w_i$ units of raw material were used for production. On the days when the plant was idle no raw material was used.
Production and disposal are parameterized by the material processing coefficient $r$. The higher the coefficient, the faster the disposal process, but the more waste is generated during raw material processing. Formally,
- If there are exactly $x$ units of waste at the end of a certain day then at the beginning of the next day there will be $x \cdot (1 - r)$ units of waste remaining.
- If there are exactly $x$ units of waste at the beginning of a day then by the end of the day there will be $x + w \cdot r$ units of waste, where $w$ is the amount of raw material used on that day.
In other words, if at the end of day $j - 1$ there are $x$ units of waste at the plant and $w_j$ units of raw material are used on day $j$ then at the end of day $j$ the amount of waste will be $(1 - r)x + r w_j$. At the beginning of the very first day there was $0$ waste.
An inspection will soon arrive at the plant. The inspection is interested in information about the amount of waste that has not yet been disposed of at the end of certain days. Unfortunately these records have been lost, so the company's management asks for your help in answering the inspection's questions based on the production data.
The first line of input contains two space-separated integers $n$ and $m$, which represent the number of days on which new waste was produced and the number of days of interest to the inspection, respectively ($1 \le n, m \le 10^5$).
The second line contains a single real number $r$, which represents the raw material processing coefficient at the plant ($0 \le r \le 1$).
Each of the next $n$ lines contains two space-separated integers $d_i$ and $w_i$, representing the number of the production day and the amount of raw material used on that day, respectively ($1 \le d_i, w_i \le 10^9$). It is guaranteed that all $d_i$ values are distinct.
The last line contains $m$ space-separated integers $q_i$, representing the days of interest to the inspection ($1 \le q_i \le 10^9$).
Output $m$ numbers each on a separate line, representing the amount of waste stored at the factory on each of the inspection days.
Your answer will be accepted if each of the output numbers has an absolute or relative error of no more than $10^{-6}$.
Input
The first line of input contains two space-separated integers $n$ and $m$, which represent the number of days on which new waste was produced and the number of days of interest to the inspection, respectively ($1 \le n, m \le 10^5$).
The second line contains a single real number $r$, which represents the raw material processing coefficient at the plant ($0 \le r \le 1$).
Each of the next $n$ lines contains two space-separated integers $d_i$ and $w_i$, representing the number of the production day and the amount of raw material used on that day, respectively ($1 \le d_i, w_i \le 10^9$). It is guaranteed that all $d_i$ values are distinct.
The last line contains $m$ space-separated integers $q_i$, representing the days of interest to the inspection ($1 \le q_i \le 10^9$).
Output
Output $m$ numbers each on a separate line, representing the amount of waste stored at the factory on each of the inspection days.
Your answer will be accepted if each of the output numbers has an absolute or relative error of no more than $10^{-6}$.
3 3
0.5
2 6
3 8
4 10
1 3 5
5 6
0.3333333
1 27
6 27
3 27
4 27
5 27
1 2 3 4 5 6
1 1
0
1 1000000000
1000000000
0 5.5 3.875
9 6 13 17.666666 20.777777 22.851851
0
Note
In the first example, the amount of waste will change as follows:
- On the first day, there is no waste.
- On the second day, the waste will be $0.5 \cdot 6 = 3$.
- On the third day, the waste will be $0.5 \cdot 3 + 0.5 \cdot 8 = 5.5$.
- On the fourth day, the waste will be $0.5 \cdot 5.5 + 0.5 \cdot 10 = 7.75$.
- On the fifth day, the plant does not produce anything new, and the waste becomes $0.5 \cdot 7.75 = 3.875$.