该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile6034.zip](file://AdditionalFile6034.zip?type=additional_file)

#6034. 「雅礼集训 2017 Day2」线段游戏

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

给出若干条线段，用 $(x_1, y_2), (x_2, y_2)$ 表示其两端点坐标，现在要求支持两种操作：

• 0 x1 y1 x2 y2 表示加入一条新的线段 $(x_1, y_2), (x_2, y_2)$；
• 1 x0 询问所有线段中，$x$ 坐标在 $x_0$ 处的最高点的 $y$ 坐标是什么，如果对应位置没有线段，则输出 $0$。

输入格式

第一行两个正整数 $n$、$m$ 为初始的线段个数和操作个数。
接下来 $n$ 行，每行四个整数，表示一条线段。
接下来 $m$ 行，每行为一个操作 0 x1 y1 x2 y2 或 1 x0。

输出格式

对于每一个询问操作，输出一行，为一个实数，当你的答案与标准答案误差不超过 $10 ^ {-2}$ 时，则视为正确。

样例

输入

3 4
0 -1 4 1
4 2 7 2
7 1 8 2
1 4
1 3
0 3 3 6 3
1 3

输出

2
0.5
3

数据范围与提示

对于 $10\%$ 的数据，$n, m \leq 1000$；
对于另外 $20\%$ 的数据，所有的 1 操作都在 0 操作之后；
对于另外 $20\%$ 的数据，所有线段的两端的 $x$ 坐标都包含所有询问的 $x$ 坐标，你可以将每条线段当做直线处理；
对于 $100\%$ 的数据，$1 \leq n \leq 50000, 1 \leq m \leq 150000$，$x_1, x_2, y_1, y_2$ 均为整数，$0 < x_0 \leq 10 ^ 5, -10 ^ 6 \leq x_1, x_2, y_1, y_2 \leq 10 ^ 6$。