처음에는 직선이 하나도 없다. 다음 두 종류의 질의를 순서대로 처리하여라.

• 1 a b : 직선 \(y = ax + b\)를 추가한다.
• 2 x : 지금까지 추가된 직선들 위에서 \(x\) 좌표가 \(x\)일 때의 \(y\) 값 중 최댓값을 출력한다.

직선이 기울기 순으로 주어지지 않고 질의의 \(x\)도 정렬되어 있지 않으므로, 스택 기반 컨벡스 헐 트릭만으로는 처리할 수 없다. 리 차오 트리 등 임의 순서 삽입을 지원하는 구조가 필요하다.

\(1 \le Q \le 100{,}000\)

\(|a|, |b| \le 10^9\), \(|x| \le 10^9\)

첫 줄에 질의의 수 \(Q\)가 주어진다.

다음 \(Q\)개의 줄에 질의가 위 형식으로 하나씩 주어진다. 첫 2번 질의 이전에 1번 질의가 한 번 이상 등장한다.

각 2번 질의의 답을 입력 순서대로 한 줄에 하나씩 출력한다.

riseoj 작성

출처 Original