Саша всё ещё любит физику. У Саши всё ещё нет друзей. Неизвестно, связаны ли эти два факта до сих пор, но Саша всё ещё очень сильно переживает из-за отсутствия товарищей. Поэтому он снова решил поразить Вадима своим экспериментом, но на этот раз немного другим.

Саша взял 2^N сосудов, поставил их в один ряд и налил в них по 1 литру сока, в i-м сосуде температура сока равна t_i. После этого он принёс эту установку Вадиму, чтобы показать эксперимент. К сожалению, Вадим до сих пор не любит физику, но его заинтересовал немного другой вопрос.

Вадим пронумеровал сосуды слева направо числами от 1 до 2^N. Он хочет узнать, сколько времени займёт смешивание сока из сосудов из отрезка с l_j-го по (l_j + 2^p_j − 1)-й по простому алгоритму:

1. Вадим берёт каждый второй сосуд и переливает его содержимое в левый от него сосуд, выкидывая эти пустые склянки из отрезка;
2. Затем он ждёт, пока в каждой склянке сок не смешался полностью и не принял общую температуру по всему сосуду;
3. Когда температура равномерно распределилась по каждому сосуду, Вадим повторяет первый шаг. Он снова переливает сок из каждого второго сосуда на отрезке в левый от него сосуд;
4. Чтобы не ждать выполнения прошлых шагов, Вадим заранее определил, какие склянки и на каком этапе алгоритма ему придётся смешать, и переливает соответствующую пару сразу после того, как температура сока в этих двух сосудах стала постоянной;
5. Вадим выполняет этот алгоритм, пока весь сок на отрезке не окажется в одном сосуде.

У Вадима есть Q вопросов такого типа, которые он спросил у Саши. Саша быстро догадался, что смешивать и проверять это всё будет довольно трудно, поэтому решил провести эксперименты в уме. Он вспомнил несколько формул из физики, которые ему пригодятся. Чтобы определить температуру сока t_f после смешивания сосудов с V₁ и V₂ литрами и t₁ и t₂ градусами сока соответственно, можно воспользоваться формулой: t_f = (V₁ · t₁ + V₂ · t₂) / (V₁ + V₂).

А чтобы определить время смешивания T_f, нужно знать коэффициент скорости смешивания одинаковых жидкостей различной температуры c_w. Для сока он равен 1 л · град / (сек). Тогда формула такая: T_f = (|t_f − t₁| · V₁ + |t_f − t₂| · V₂) / c_w.

Саша расстроился, что провести эти вычисления в голове очень трудно, поэтому он и просит помощи у Вас.

В первой строке даны два целых числа N и Q — число, используемое для описания количества сосудов, и количество вопросов, заданных Вадимом (1 ≤ N ≤ 18, 1 ≤ Q ≤ 10⁵).

Во второй строке через пробел даны 2^N целых чисел t_i — температуры сока в сосудах (0 ≤ t_i ≤ 10⁵).

В следующих Q строках описываются вопросы Вадима двумя целыми числами l_j и p_j, им соответствует отрезок [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).

Выведите Q чисел — время, затраченное на смешивание по предложенному Вадимом алгоритму, в секундах в порядке ввода.

Ответ будет засчитан, если абсолютная или относительная погрешность значений не превосходит 10⁻⁹. Формально, пусть ваш ответ равен x, а ответ жюри равен y. Ваш ответ считается правильным, если |x−y| / max(1,|y|) ≤ 10⁻⁹.