题目描述

Deni 正沿着从索菲亚到瓦尔纳的高速公路旅行。道路上有很多限速标志，以及一种实验性的“取消最后一个生效限速”的标志。

这种取消标志与现实中的普通取消限速标志不同：它只取消当前生效的限速，并恢复到当前限速出现之前的那个限速。如果不存在这样的限速，那么默认最大速度为 $120$ km/h。每个标志从它出现的位置开始生效，直到下一个标志出现，或直到道路终点。

Deni 已经多次走过这条路，因此预先知道路上会遇到的所有 $N$ 个标志。我们认为她从第 $0$ 公里处出发，道路总长度为 $L$。

由于 Deni 有一场非常重要的会议，她希望在遵守限速的前提下尽快到达终点。与此同时，会收到 $Q$ 个关于临时改变某个标志的信号。每个信号只在该信号对应的问题中生效，不影响后续信号。也就是说，对于每个信号，都从原始标志序列出发，只修改其中一个标志。

请对每个信号，求出在该信号生效时，Deni 从起点到终点所需的最短时间。

保证在原始标志序列中，以及在每个信号修改后的标志序列中，如果某段路的当前限速是默认限速 $120$ km/h，那么下一块标志不会是“取消最后一个生效限速”的标志。

输入格式

第一行输入两个整数 $N,L$，分别表示标志数量和道路总长度。

接下来 $N$ 行，每行输入两个整数 $d_i,s_i$，表示第 $i$ 个标志位于距离起点 $d_i$ 公里处，类型为 $s_i$：

• 若 $s_i=-1$，表示这是“取消最后一个生效限速”的标志；
• 否则表示这是一个最大速度为 $s_i$ km/h 的限速标志。

接下来一行输入一个整数 $Q$，表示信号数量。

接下来 $Q$ 行，每行输入两个整数 $p_j,s'_j$，表示在第 $j$ 个信号中，将位置编号为 $p_j$ 的标志临时改为类型 $s'_j$。

注意：$p_j$ 是标志在序列中的编号，不是道路上的公里数。

输出格式

输出 $Q$ 行。第 $j$ 行输出一个实数，表示第 $j$ 个信号生效时，从起点到终点所需的最短时间。

若你的答案与标准答案的绝对误差小于 $10^{-3}$，则认为正确。

建议至少输出到小数点后四位，例如：

cout << fixed << setprecision(4) << ans;

数据范围

• $1\le N\le 10^5$；
• $1\le Q\le 10^5$；
• $N+1\le L\le 10^9$；
• $0<d_1<d_2<\cdots<d_N<L$；
• $s_i,s'_j$ 要么为 $-1$，要么为 $[10,119]$ 中的整数；
• $1\le p_j\le N$。

子任务

只有通过某个子任务中的所有测试点，才能获得该子任务的分数。

样例

输入

7 2070
120 10
170 20
270 30
420 -1
620 50
870 -1
1170 100
11
1 25
2 25
3 25
4 25
5 25
6 25
7 25
2 -1
3 -1
5 -1
7 -1

输出

52.0000
49.0000
56.0000
50.0000
60.0000
52.0000
82.0000
30.0000
44.1667
62.5000
136.0000

样例解释

以第一个信号为例，修改后的标志类型依次为：

此时各路段的生效限速依次为：

• $[0,120]$：$120$ km/h，用时 $1$ 小时；
• $[120,170]$：$25$ km/h，用时 $2$ 小时；
• $[170,270]$：$20$ km/h，用时 $5$ 小时；
• $[270,420]$：$30$ km/h，用时 $5$ 小时；
• $[420,620]$：$20$ km/h，用时 $10$ 小时；
• $[620,870]$：$50$ km/h，用时 $5$ 小时；
• $[870,1170]$：$20$ km/h，用时 $15$ 小时；
• $[1170,2070]$：$100$ km/h，用时 $9$ 小时。

因此总用时为