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 functions in the set, find the maximum/minimum value of { fi(x)) }.

You also have some special constriants 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 queries 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 -1
1 3 -2
2 -1
2 3 Output:
-5
7


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