The users with the highest PP on the DMOJ.

The DMOJ is a source of countless debates on how to accurately rank users from best to worst. One measurement, called PP, catches the attention of Nathan.

The problems on the DMOJ are numbered from ~1~ to ~100\,000~. When a user submits to a problem, the user will be given a point value (a real number between ~0~ and ~10\,000~ inclusive), but only the highest point value reached for that problem will be considered in the rankings. A user will get ~0~ points from a problem with ~0~ submissions.

To measure the PP of a user, the first step is to get all of the user's points as a list. Then, this list is sorted in non-increasing order. For simplicity, this sequence will be labelled from ~s_1~ to ~s_{100\,000}~.

The actual calculations can now begin, with the result starting at ~0~, and ~r~ ~(0 < r \le 1)~ as a given ratio. In the ~1^\text{st}~ step, the result increases by ~s_1 \cdot r^0~ (it is known that ~r^0 = 1~). In the ~2^\text{nd}~ step, the result increases by ~s_2 \cdot r^1~. In general, the result increases by ~s_i \cdot r^{i-1}~. This continues until the list is exhausted, and the final result is the user's PP.

In other words, a user's PP is equal to ~\sum_{i=1}^{100\,000} s_i \cdot r^{i-1}~.

Although it is nice to sort everyone by PP, Nathan does not want to stop there. He wants to plot a user's PP against the date. Since Nathan's code somehow crashes on a user with ~N~ submissions, can you calculate the information for him?

Constraints

In all subtasks, ~1 \le N \le 200\,000~.

Subtask	Points	Additional Constraints
1	5	~P_i = 1~
2	10	~N \le 500~ Also, ~1 \le P_i \le 500~. In other words, the user will only make submissions to problems in the range ~1 \dots 500~.
3	10	~r = 1~
4	20	~r \le 0.01~
5	30	~N \le 80\,000~
6	25	No additional constraints.

Input Specification

The first line contains a real number ~r~ ~(10^{-6} \le r \le 1)~, a ratio given to 6 decimal places.

The second line contains ~N~, the number of submissions that a user made.

~N~ lines of input follow. The ~i^\text{th}~ line contains an integer, ~P_i~ ~(1 \le P_i \le 100\,000)~, followed by a real number given to three decimal places, ~V_i~ ~(0 \le V_i \le 10\,000)~. This signifies that on the ~i^\text{th}~ submission, the user submitted to problem number ~P_i~ and received a point value of ~V_i~.

Output Specification

The output will consist of ~N~ lines. On the ~i^\text{th}~ line, output the user's PP directly after their ~i^\text{th}~ submission.

Your answer will be judged as correct if the absolute or relative error does not exceed ~10^{-7}~.

Sample Input 1

0.500000
5
2 4.000
1 6.000
2 10.000
3 2.000
3 0.000

Sample Output 1

4.000000000
8.000000000
13.000000000
13.500000000
13.500000000

Explanation for Sample Output 1

After the ~1^\text{st}~ submission, ~s_1 = 4~ and the remaining terms are ~0~. Therefore, the user's PP is ~4 \cdot 1 = 4~.

After the ~2^\text{nd}~ submission, ~s_1 = 6~, ~s_2 = 4~, and the remaining terms are ~0~. Therefore, the user's PP is ~6 \cdot 1 + 4 \cdot 0.5 = 8~.

After the ~3^\text{rd}~ submission, problem ~2~ gets bumped from ~4~ to ~10~. As a result, ~s_1 = 10~, ~s_2 = 6~, and the remaining terms are ~0~. Therefore, the user's PP is ~10 \cdot 1 + 6 \cdot 0.5 = 13~.

After the ~4^\text{th}~ submission, the user's PP is ~10 \cdot 1 + 6 \cdot 0.5 + 2 \cdot 0.25 = 13.5~.

The ~5^\text{th}~ submission does not change the sequence ~s~, therefore the user's PP stays the same.

Sample Input 2

0.010000
8
1 1.000
2 2.000
3 3.000
4 4.000
5 5.000
6 6.000
3 2.000
3 5.000

Sample Output 2

1.000000000
2.010000000
3.020100000
4.030201000
5.040302010
6.050403020
6.050403020
6.050504020