직선의 최솟값

빈 직선 집합 $S$가 있다. $Q$개의 쿼리를 순서대로 처리하라.

쿼리는 다음 중 하나이다.

• 1 a b: 직선 $y=ax+b$를 $S$에 추가한다. $(-10^9 \leq a,b \leq 10^9)$
• 2 x: $S$에 있는 직선 중 $x$에서의 $y$값의 최솟값을 출력한다. $(-10^9 \leq x \leq 10^9)$

첫 번째 줄에 쿼리의 개수 $Q$가 주어진다. $(1 \leq Q \leq 200\,000)$

두 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 하나씩 주어진다.

1 a b 쿼리에서 추가되는 직선의 기울기 $a$는 입력 순서대로 엄격하게 감소한다.

2 x 쿼리의 $x$는 직선이 하나 이상 추가된 뒤에만 주어진다.

2 x 쿼리마다 최솟값을 한 줄에 하나씩 출력한다.