Джонни участвует в карнавале, на котором проводится n лотерей. В ходе лотереи с номером i разыгрывается приз ценностью pi. Каждый участник покупает сколько-то лотерейных билетов, а затем произвольным образом распределяет их между n лототронами. В конце карнавала из каждого лототрона случайным образом достают один билет, и его обладатель выигрывает соответствующий приз. Один человек вполне может выиграть и несколько призов с разных лототронов.
Правила карнавальных лотерей запрещают одному участнику владеть более чем половиной билетов в лототроне, то есть никто не может положить в один лототрон больше билетов, чем все остальные участники вместе взятые. В начале лотереи организаторы кладут в каждый лототрон один билет и не извлекают его оттуда до конца карнавала.
Джонни купил t лотерейных билетов и теперь думает, как же распределить их по лототронам. Сейчас в i-м лототроне находится li билетов. Джонни наблюдает, как остальные участники лотереи время от времени меняют свои решения и перемещают по одному билету. После каждого такого перемещения Джонни хочет знать максимальное математическое ожидание выигрыша, которого он может добиться, разместив билеты оптимальным способом. Разумеется, Джонни не может использовать больше чем t билетов и нарушать правила лотереи, помещая в один лототрон больше билетов, чем все остальные участники лотереи вместе взятые.
В первой строке входных данных записаны числа n, t и q (1 ≤ n, t, q ≤ 200 000) — количество лототронов, количество билетов в распоряжении Джонни и количество изменений соответственно.
Во второй строке записаны n чисел pi (1 ≤ pi ≤ 1000), i-е из которых задаёт ценность приза в i-й лотерее.
В третьей строке записано n чисел li (1 ≤ li ≤ 1000) — изначальное количество билетов в каждом лототроне.
Далее следуют q строк с описанием изменений. Каждое описание состоит из двух целых чисел tk и rk (1 ≤ tk ≤ 2, 1 ≤ rk ≤ n) — тип изменения и номер лототрона. Если tk = 1, то кто-то добавляет один билет в лототрон rk, а если tk = 2, то кто-то убирает билет из лототрона rk.
Гарантируется, что после любой операции в каждом лототроне есть хотя бы 1 билет.
Выведите q строк, каждая строка должна содержать одно вещественное число — максимально возможное математическое ожидание выигрыша Джонни после выполнения первых k изменений. Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не будет превосходить 10 - 6.
А именно: пусть ваш ответ равен a, а ответ жюри — b. Проверяющая программа будет считать ваш ответ правильным, если 
.
2 1 3
4 5
1 2
1 1
1 2
2 1
1.666666667
1.333333333
2.000000000
3 20 5
6 8 10
6 6 6
1 1
1 2
1 3
2 3
2 3
12.000000000
12.000000000
11.769230769
12.000000000
12.000000000
В первом примере у Джонни есть только один билет. Призы имеют ценность 4 и 5, а в лототронах изначально находятся 1 и 2 билета соответственно. После первого изменения в каждом лототроне лежит по 2 билета, так что если Джонни поместит свой билет во второй лототрон, то математическое ожидание выигрыша будет равно 
. После второго изменения во втором лототроне находится три билета, так что наиболее выгодной стратегией будет положить билет в первый лототрон — математическое ожидание выигрыша равно 
. После третьего изменения Джонни должен положить свой билет в первый лототрон, тогда математическое ожидание выигрыша равно 
.
Во втором примере у Джонни больше билетов, чем он может использовать по правилам карнавальной лотереи. Например, после первого изменения, в лототронах лежат 7, 6 и 6 билетов соответственно, так что Джонни может использовать только 19 своих билетов и выиграть каждый приз с вероятностью 
.
| 8VC Venture Cup 2016 - Elimination Round |
|---|
| Закончено |
