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 { f_i(x)) }.

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

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

Furthermore, all queries of second kind will obey this - x_i < x_i+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