ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

2170. Experiment with Juice 2

Time limit: 3.0 second
Memory limit: 512 MB
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 2N 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 ti. 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 2N. He wants to know how much time it will take to mix the juice from the vessels in the range from the lj-th to the (lj + 2pj − 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 tf after mixing vessels with V1 and V2 liters and juices with temperatures t1 and t2 degrees respectively, you can use the formula:
tf = (V1 · t1 + V2 · t2) / (V1 + V2).
And to determine the mixing time Tf, you need to know the mixing rate coefficient for identical liquids with different temperatures cw. For juice, it is equal to 1 l · deg / sec. Then the formula is as follows:
Tf = (|tft1| · V1 + |tft2| · V2) / cw.
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 ≤ 105).
The second line contains 2N integers ti separated by spaces — the temperatures of the juice in the vessels (0 ≤ ti ≤ 105).
The next Q lines describe Vadim’s questions with two integers lj and pj, corresponding to the interval [lj; lj + 2pj − 1] (1 ≤ lj ≤ 2N, 0 ≤ pjN, lj + 2pj − 1 ≤ 2N).


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−9. Formally, let your answer be x, and the jury’s answer be y. Your answer is considered correct if |xy| / max(1,|y|) ≤ 10−9.


2 2
1 2 3 4
2 1
1 2
Problem Author: Vadim Barinov
Problem Source: Ural School Programming Contest 2022