## CHTPRAC - CHT Practice

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 **{ f _{i}(x)) }. **

You also have some special constrians 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**, and all queries are for maximum.

_{i}> m_{i+1}3.

**m**, and all queries are for minimum.

_{i}< m_{i+1}4.

**m**, and all queries are for maximum.

_{i}< m_{i+1}Furthermore, all quereis 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 3Output:

-5

7

Added by: | Rezwan |

Date: | 2018-03-02 |

Time limit: | 1s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All |