Как-то раз два студента Гриша и Диана оказались в химической лаборатории университета. В лаборатории ребята нашли n колб c ртутью, пронумерованных от 1 до n, и решили провести эксперимент.
Эксперимент состоит из q шагов. На каждом шаге выполняется одно из следующих действий:
- Диана выливает все содержимое из колбы номером pi, а затем заливает туда ровно xi литров ртути.
- Рассмотрим все возможные способы долить vi литров воды в колбы; для каждого способа посчитаем, сколько жидкости (вода и ртуть) содержит колба с водой с максимальным количеством жидкости; среди всех вычисленных чисел найдем минимальное. Ребята хотят посчитать описанное значение. При подсчетах ребята ничего никуда не доливают на самом деле. Все подсчеты они делают, не изменяя содержимое колб.
К сожалению, оказалось, что вычисления слишком громоздкие, поэтому ребята обратились за помощью к вам. Помогите ребятам провести описанный эксперимент.
Выходные данные
Для каждого действия второго вида вам нужно вывести подсчитанное значение. Ответ будет считаться правильным, если относительная или абсолютная погрешность не будет превышать 10 - 4.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 2 0
2 2
1 2 1
2 3
|
1.50000
1.66667
|
|
2
|
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
|