You are on North Terrace waiting for your bus home in winter. It's peak hour and the traffic is heavily backed up, so you expect your bus to be delayed at least 30 minutes. However, you are enjoying the winter vibes while listening to the ACPC playlist, so you are internally at peace. To pass the time, you decide to play a game using the intermittent rainfall.

In your bag you have a bunch of buckets of variable sizes, and you want to make a big line with them the model water flow. You also fix a plane of wood to each side, so overflow can only flow into the other buckets or over the ends. Then, you wait for rainfall. In this spot, rain is extremely localised, so each burst of rain only falls into a single bucket. The buckets fills up with rain, but if rain goes into a bucket that is already full, the excess will split into two halves and flow evenly to the left and right until it finds enough capacity or reaches the end. Any water that spills over the ends are lost. After the rain clears up, your bus still hasn't arrived, so you want to count the rain in each of the buckets. However, you don't want to look in the buckets, you want to only use your knowledge of the bucket sizes and rain events to calculate it.

Input

The first input contains two integers ~n~ and ~q~, where ~n~ ~(1 \leq n \leq 10^5)~ is the number of buckets and ~q~ ~(1 \leq q \leq 10^5)~ is the number of bursts of rain. The buckets are labelled ~1~ through to ~n~.

The next line contains ~n~ space-separated integers ~c_i~ ~(1 \leq c_i \leq 10^5)~, the capacity of each of the buckets.

The next ~q~ lines each contain information about the rainfall. Each line has two integers ~a_i~ ~(1 \leq a_i \leq n)~, the target of the rainfall, and ~x_i~ ~(1 \leq x_i \leq 10^9)~, the amount of rain.

Output

On separate lines, report the amount of rain in each of the ~n~ buckets once all the rainfall events have happened. Each of your outputs needs to be within ~10^{-6}~ absolute difference of the correct value.

Clarifications

• If the bucket overflows from the rainfall, the excess will split into two equal halves and flow left and right. However, subsequent overflows won't come back towards the bucket where rain was as they will continue in a single direction only.

Example

Input 1

3 1
5 5 5
2 10

Output 1

2.5
5
2.5

There is only one rainfall burst on the middle bucket. The first ~5~ fills up that bucket, and the remaining ~5~ gets split and overflows, leading to the other two buckets having ~2.5~.

Input 2

4 1
3 3 3 3
1 10

Output 2

3
3
0.5
0

There is only one rainfall event. It fills the first bucket, and the remaining ~7~ gets split into ~3.5~ and ~3.5~. One of the overflows spills over the edge, getting lost, while the remaining spills to the right. It completely fills another bucket with ~3~ water, and then the remaining ~0.5~ goes into the third.

Input 3

4 2
2 4 2 4
2 10
4 2

Output 3

2
4
2
3

The first rainfall fills the second bucket and splits into two parts of ~3~. The left part fills the first bucket and then spills over the edge. The right part filles the third bucket, and then fills the fourth bucket with ~1~. Then the next rainfall completely fits in the fourth bucket, filling it to ~3~.