Sasha still loves physics. Sasha still has no friends. It is still unknown if these two facts are related, but Sasha is still very upset about the lack of companions. Therefore, he decided to impress Vadim with his experiment again, but this time a little different.

Sasha took 2^N vessels, placed them in a row, and poured 1 liter of juice into each vessel, with the temperature of the juice in the i-th vessel being t_i. After that, he brought this setup to Vadim to demonstrate the experiment. Unfortunately, Vadim still doesn’t like physics, but he was interested in a slightly different question.

Vadim numbered the vessels from left to right with numbers from 1 to 2^N. He wants to know how much time it will take to mix the juice from the vessels in the range from the l_j-th to the (l_j + 2^p_j − 1)-th using a simple algorithm:

1. Vadim takes every second vessel and pours its contents into the vessel to its left, discarding these empty vessels from the range;
2. Then he waits until the juice in each vessel is fully mixed and reaches a common temperature throughout the vessel;
3. When the temperature is evenly distributed in each vessel, Vadim repeats the first step. He pours the juice from every second vessel in the range into the vessel to its left;
4. To avoid waiting for the previous steps to complete, Vadim has determined in advance which vessels and at which stage of the algorithm he will have to mix, and pours the corresponding pair as soon as the temperature of the juice in these two vessels becomes constant;
5. Vadim performs this algorithm until all the juice in the range ends up in one vessel.

Vadim has Q questions of this type that he asked Sasha. Sasha quickly realized that mixing and checking all of this would be quite difficult, so he decided to conduct mental experiments. He remembered several formulas from physics that would come in handy. To determine the temperature of the juice t_f after mixing vessels with V₁ and V₂ liters and juices with temperatures t₁ and t₂ degrees respectively, you can use the formula: t_f = (V₁ · t₁ + V₂ · t₂) / (V₁ + V₂).

And to determine the mixing time T_f, you need to know the mixing rate coefficient for identical liquids with different temperatures c_w. For juice, it is equal to 1 l · deg / sec. Then the formula is as follows: T_f = (|t_f − t₁| · V₁ + |t_f − t₂| · V₂) / c_w.

Sasha was upset that performing these calculations in his head is very difficult, so he asks for your help.

The first line contains two integers N and Q — the number used to describe the number of vessels and the number of questions asked by Vadim (1 ≤ N ≤ 18, 1 ≤ Q ≤ 10⁵).

The second line contains 2^N integers t_i separated by spaces — the temperatures of the juice in the vessels (0 ≤ t_i ≤ 10⁵).

The next Q lines describe Vadim’s questions with two integers l_j and p_j, corresponding to the interval [l_j; l_j + 2^p_j − 1] (1 ≤ l_j ≤ 2^N, 0 ≤ p_j ≤ N, l_j + 2^p_j − 1 ≤ 2^N).

Output Q numbers — the time taken to mix the juice according to Vadim’s algorithm, in seconds, in the order of input.

The answer will be accepted if the absolute or relative error of the values does not exceed 10⁻⁹. Formally, let your answer be x, and the jury’s answer be y. Your answer is considered correct if |x−y| / max(1,|y|) ≤ 10⁻⁹.