Half-plane land grab

Time limit2sMemory limit128 MB

Summary

Lines are added one at a time, and after each addition you must report the maximum y value over all added lines at a given x.

Level: Hard8 of 10
Topics: Geometry, Dynamic programming, Binary search
Solved: No attempts yet

Problem

You play a land grab game on an infinite two-dimensional plane. Each turn you flick a stone, and the stone flies forever along the line $y = ax + b$ . That line cuts the plane into two parts, and you capture the whole part that contains $(0, -\infty)$ , meaning everything below the line.

Land you have captured stays captured. The land you hold at any moment is therefore the union of the lower half-planes of every line flicked so far.

Between flicks you want to know how high your captured land reaches at a given x coordinate. The flicks and the questions are given in chronological order. Answer every question.

Input

The first line contains the number of records $Q$ ( $1 \le Q \le 200000$ ). Each of the next $Q$ lines contains one record, in chronological order.

A record 1 a b means a stone was flicked along the line $y = ax + b$ ( $|a| \le 10^6$ , $|b| \le 10^{12}$ ).
A record 2 x asks for the highest y coordinate of a captured point whose x coordinate is $x$ , using only the flicks made so far ( $|x| \le 10^{12}$ ).

The first record always starts with 1. Every input value is an integer.

Output

For each record starting with 2, print its answer on its own line, in the order the questions appear. Every answer is an integer.

Examples4

Example 1
Input
```
4
1 1 2
1 2 3
2 -100
2 100
```
Expected output
```
-98
203
```
Example 2
Input
```
2
1 0 0
2 0
```
Expected output
```
0
```

Example 3

Input

4
1 1000000 1000000000000
1 -1000000 -1000000000000
2 1000000000000
2 -1000000000000

Expected output

1000001000000000000
999999000000000000

Example 4
Input
```
5
1 3 1
1 -2 11
2 2
2 1
2 3
```
Expected output
```
7
9
10
```