题目描述

给 $N$ 个抛物线 （只会完整地存在在第一象限，不在第一象限的部分不需考虑，如图） 。

询问 $M$ 次，每次询问第 $i$ 到第 $j$ 个抛物线在 $[l,r]$ 的 $x$ 坐标区间上的最小值。

输入格式

所有输入均为整数。
第一行 $N$ 一个整数。
接下来 $N$ 行，每行 $p,x,y$ 表示抛物线左边界的 $x$ 坐标，顶点的 $x,y$ 坐标区间上的最小值。
接下来 $M$ 一个整数。
接下来 $M$ 行，每行 $i,j,l,r$ 如题意所示。

输出格式

$M$ 行每行一个实数，表示第 $M$ 次询问的答案，误差 $<1^{-4}$ 即可。

2
10 30 10
20 30 30
4
1 2 0 11
1 2 20 25
1 2 25 35
1 2 45 100

0.975
22.5
30.0
4.375
 

数据规模与约定

对于 $100\%$ 的数据，$1 \leq n \leq 5 \times 10^4$， $0 \leq p < x \leq 5 \times 10^4$， $0 < y \leq 50$， $1 \leq m \leq 2 \times 10^4$， $0 \leq l \leq r \leq 5 \times 10^4$， $1 \leq a \leq b \leq n$。

题目来源

鸣谢Kac