## CHTPRAC - CHT Practice

no tags

You can test you CHT implementation in this problem. Problem is simple. You have to solve some queries in the form -

1 m b: Add a function f(x) = mx + b in a set.
2 x: For all existing funciton in the set, find the maximum/minimum value of { fi(x)) }.

You also have some special constrians on the inputs. In a dataset, you have either of the four cases for all queries -

1. mi > mi+1, and all queries are for minimum.
2. mi > mi+1, and all queries are for maximum.
3. mi < mi+1, and all queries are for minimum.
4. mi < mi+1, and all queries are for maximum.

Furthermore, all quereis of second kind will obey this - xi < xi+1.

### Input

In the first line, you will have a number Q <= 10^5, the number of queries. Then a integer a, where a denotes the case number (from problem statement), which you'll need to handle in this dataset.

Next Q lines will contain a number t first, if it is 1 then another two integers will be given m b, where |m|, |b|<= 10^9. Then you need to add the function f(x) = mx + b into set.
if t is 2, then you will be given a number |x| <= 10^9, you need to answer the query as described.

### Output

For each query of second type, print the desired answer in a seperate line.

### Example

```Input:
5 1 1 5 1 1 4 -11 3 -22 -12 3

Output:-57 ```

 Added by: Rezwan Date: 2018-03-02 Time limit: 1s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All