Half-plane land grab

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.

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.

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