반평면 땅따먹기

무한히 넓은 2차원 평면에서 땅따먹기를 한다. 한 번 돌을 치면 돌은 직선 $y = ax + b$를 따라 무한히 날아가고, 그 직선이 평면을 나누는 두 영역 중 $(0, -\infty)$를 포함하는 쪽, 즉 직선 아래쪽 영역을 전부 점령한다.

한 번 점령한 땅은 계속 남는다. 따라서 어느 시점에 점령하고 있는 땅은 그때까지 날린 모든 직선의 아래쪽 반평면을 합친 영역이다.

돌을 날리는 사이사이에, 특정 x좌표에서 점령한 땅이 가장 높이 올라간 y좌표를 알고 싶다. 돌을 날린 기록과 질문이 시간 순서로 주어질 때, 질문마다 답을 구하라.

첫 줄에 기록의 개수 $Q$($1 \le Q \le 200000$)가 주어진다. 이어지는 $Q$개의 줄에 기록이 시간 순서로 하나씩 주어진다.

• 1 a b 형태의 줄은 직선 $y = ax + b$를 따라 돌을 날렸다는 뜻이다. ($|a| \le 10^6$, $|b| \le 10^{12}$)
• 2 x 형태의 줄은 그 시점까지 점령한 땅 중 x좌표가 $x$인 점의 가장 높은 y좌표를 묻는다. ($|x| \le 10^{12}$)

첫 번째 기록은 항상 1로 시작한다. 입력의 모든 값은 정수다.

2로 시작하는 기록마다 그 시점의 답을 한 줄에 하나씩, 질문이 나온 순서대로 출력한다. 답은 항상 정수다.