E. Химический эксперимент
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как-то раз два студента Гриша и Диана оказались в химической лаборатории университета. В лаборатории ребята нашли n колб c ртутью, пронумерованных от 1 до n, и решили провести эксперимент.

Эксперимент состоит из q шагов. На каждом шаге выполняется одно из следующих действий:

  1. Диана выливает все содержимое из колбы номером pi, а затем заливает туда ровно xi литров ртути.
  2. Рассмотрим все возможные способы долить vi литров воды в колбы; для каждого способа посчитаем, сколько жидкости (вода и ртуть) содержит колба с водой с максимальным количеством жидкости; среди всех вычисленных чисел найдем минимальное. Ребята хотят посчитать описанное значение. При подсчетах ребята ничего никуда не доливают на самом деле. Все подсчеты они делают, не изменяя содержимое колб.

К сожалению, оказалось, что вычисления слишком громоздкие, поэтому ребята обратились за помощью к вам. Помогите ребятам провести описанный эксперимент.

Входные данные

В первой строке записано два целых числа n и q (1 ≤ n, q ≤ 105) — количество колб и шагов эксперимента. В следующей строке, через пробел, записано n целых чисел: h1, h2, ..., hn (0 ≤ hi ≤ 109), где hi — это объем ртути в і-й колбе в начале эксперимента.

В следующих q строках записаны действия игры в следующем формате:

  • Строка вида «1 pi xi» обозначает действие первого вида (1 ≤ pi ≤ n; 0 ≤ xi ≤ 109).
  • Строка вида «2 vi» обозначает действие второго вида (1 ≤ vi ≤ 1015).

Гарантируется, что есть хотя бы одно действие второго вида. Гарантируется, что все числа описывающие действия эксперимента целые.

Выходные данные

Для каждого действия второго вида вам нужно вывести подсчитанное значение. Ответ будет считаться правильным, если относительная или абсолютная погрешность не будет превышать 10 - 4.

Примеры
Входные данные
3 3
1 2 0
2 2
1 2 1
2 3
Выходные данные
1.50000
1.66667
Входные данные
4 5
1 3 0 1
2 3
2 1
1 3 2
2 3
2 4
Выходные данные
1.66667
1.00000
2.33333
2.66667