CF626G.Raffles

Johnny is at a carnival which has n raffles. Raffle i has a prize with value p__i. Each participant can put tickets in whichever raffles they choose (they may have more than one ticket in a single raffle). At the end of the carnival, one ticket is selected at random from each raffle, and the owner of the ticket wins the associated prize. A single person can win multiple prizes from different raffles.

However, county rules prevent any one participant from owning more than half the tickets in a single raffle, i.e. putting more tickets in the raffle than all the other participants combined. To help combat this (and possibly win some prizes), the organizers started by placing a single ticket in each raffle, which they will never remove.

Johnny bought t tickets and is wondering where to place them. Currently, there are a total of l__i tickets in the i-th raffle. He watches as other participants place tickets and modify their decisions and, at every moment in time, wants to know how much he can possibly earn. Find the maximum possible expected value of Johnny's winnings at each moment if he distributes his tickets optimally. Johnny may redistribute all of his tickets arbitrarily between each update, but he may not place more than t tickets total or have more tickets in a single raffle than all other participants combined.

约翰尼正在参加一个有 $n$ 个抽奖活动的游园会。第 $i$ 个抽奖活动的奖品价值为 $p_i$。每位参与者可以将彩票投入任意数量的抽奖活动中（即，可在同一个抽奖活动中投入多张彩票）。游园会结束时，每个抽奖活动会随机抽取一张彩票，该彩票的持有者赢得对应奖品。同一个人可能从多个不同的抽奖活动中赢得多个奖品。

然而，该县法规禁止任何一名参与者在单个抽奖活动中持有的彩票数超过该抽奖活动总票数的一半，即：某参与者在某个抽奖活动中投入的票数不能超过其他所有参与者在该抽奖活动中投入票数的总和。为应对这一限制（并可能赢得一些奖品），主办方在每个抽奖活动开始时预先投入了一张彩票，且这张彩票永远不会被移除。

约翰尼购买了 $t$ 张彩票，并在思考应如何分配它们。目前，第 $i$ 个抽奖活动中已有 $l_i$ 张彩票。他观察着其他参与者不断投入彩票并调整他们的策略；在每一时刻，他都想知道自己最多能获得多少收益。请计算在每一时刻，若约翰尼以最优方式分配他的彩票，其获奖收益的最大可能期望值是多少。约翰尼可以在每次更新后重新任意分配他全部的彩票（即不继承之前的分配），但总票数不得超过 $t$ 张，且在任一抽奖活动中，他投入的票数不得超过当时其他所有参与者在该抽奖活动中投入票数的总和。

The first line contains two integers n, t, and q (1 ≤ n, t, q ≤ 200 000) — the number of raffles, the number of tickets Johnny has, and the total number of updates, respectively.

The second line contains n space-separated integers p__i (1 ≤ p__i ≤ 1000) — the value of the i-th prize.

The third line contains n space-separated integers l__i (1 ≤ l__i ≤ 1000) — the number of tickets initially in the i-th raffle.

The last q lines contain the descriptions of the updates. Each description contains two integers t__k, r__k (1 ≤ t__k ≤ 2, 1 ≤ r__k ≤ n) — the type of the update and the raffle number. An update of type 1 represents another participant adding a ticket to raffle r__k. An update of type 2 represents another participant removing a ticket from raffle r__k.

It is guaranteed that, after each update, each raffle has at least 1 ticket (not including Johnny's) in it.

第一行包含三个整数 $n$、$t$ 和 $q$（$1 ≤ n, t, q ≤ 200\,000$），分别表示抽奖活动的数量、Johnny 拥有的彩票数量以及更新操作的总次数。

第二行包含 $n$ 个用空格分隔的整数 $p_i$（$1 ≤ p_i ≤ 1000$），表示第 $i$ 个奖品的价值。

第三行包含 $n$ 个用空格分隔的整数 $l_i$（$1 ≤ l_i ≤ 1000$），表示第 $i$ 个抽奖活动中初始拥有的彩票数量。

接下来的 $q$ 行描述了每次更新操作。每行包含两个整数 $t_k$ 和 $r_k$（$1 ≤ t_k ≤ 2$，$1 ≤ r_k ≤ n$），分别表示更新操作的类型和所涉及的抽奖活动编号。类型为 1 的更新表示另一位参与者向抽奖活动 $r_k$ 中添加一张彩票；类型为 2 的更新表示另一位参与者从抽奖活动 $r_k$ 中移除一张彩票。

保证在每次更新操作之后，每个抽奖活动（不包括 Johnny 的彩票）中至少有 1 张彩票。

Print q lines, each containing a single real number — the maximum expected value of Johnny's winnings after the k-th update. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if .

输出 q 行，每行包含一个实数——即 Johnny 在第 k 次更新后的最大期望收益。若你的答案的绝对误差或相对误差不超过 10 - 6，则视为正确。

具体而言：假设你的答案为 a，评测组的标准答案为 b。当满足 时，评测程序将判定你的答案正确。

In the first case, Johnny only has one ticket to distribute. The prizes are worth 4 and 5, and the raffles initially have 1 and 2 tickets, respectively. After the first update, each raffle has 2 tickets, so Johnny has expected value of winning by placing his ticket into the second raffle. The second update adds a ticket to the second raffle, so Johnny can win in the first raffle. After the final update, Johnny keeps his ticket in the first raffle and wins .

In the second case, Johnny has more tickets than he is allowed to spend. In particular, after the first update, there are 7, 6, and 6 tickets in each raffle, respectively, so Johnny can only put in 19 tickets, winning each prize with probability . Also, note that after the last two updates, Johnny must remove a ticket from the last raffle in order to stay under the tickets in the third raffle.

在第一种情况下，约翰尼只有一张票可以分配。奖品价值分别为 4 和 5，而两个抽奖活动初始分别有 1 张和 2 张票。第一次更新后，每个抽奖活动均有 2 张票，因此若约翰尼将他的票投入第二个抽奖活动，则其获胜的期望值为 。第二次更新向第二个抽奖活动中增加了一张票，因此约翰尼若将票投入第一个抽奖活动，则可赢得 。最后一次更新后，约翰尼将其票保留在第一个抽奖活动中，并赢得 。

在第二种情况下，约翰尼拥有的票数超过了他被允许使用的数量。具体而言，第一次更新后，三个抽奖活动中的票数分别为 7、6 和 6，因此约翰尼最多只能投入 19 张票，且赢得每个奖品的概率均为 。此外请注意，在最后两次更新之后，为确保第三个抽奖活动中的票数不超过 ，约翰尼必须从最后一个抽奖活动中移除一张票。