题目描述

要求在平面直角坐标系下维护两个操作：

1. 在平面上加入一条直线。
2. 给定一个数 $k$，询问与直线 $x = k$ 相交的线段中，交点纵坐标最大的纵坐标值。

输入格式

输入的第一行是两个整数 $a,b$，代表最初有一条 $y=ax+b$ 的直线。 输入的第二行是一个整数 $m$，代表操作的个数。

接下来 $m$ 行，每行若干个用空格隔开的整数，第 $i + 1$ 行的第一个整数为 $op$，代表第 $i$ 次操作的类型。

若 $op = 1$，则后跟两个整数 $a,b$，表示插入了一条 $y=ax+b$ 的直线。

若 $op = 2$，则后跟一个整数 $k$，代表本次操作为查询所所有与直线 $x=k$ 相交的线段中，交点纵坐标最大的线段编号。

输出格式

对于每次查询，输出一行一个整数，代表交点纵坐标最大的纵坐标值。

样例 #1

样例输入 #1

1 1
10
2 5
1 4 2
2 1000
1 -30 2
2 2343
2 10000
1 -35 250
2 1515
1 789 2
2 1010

样例输出 #1

6
4002
9374
40002
6062
796892

数据范围与约定

对于 $30\%$ 的数据，保证 $m \leq 10^3$。

对于 $100\%$ 的数据，保证 $1 \leq m \leq 10^5$，$1 \leq k \leq 10^5$，$1 \leq y \leq 10^9$。