시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 850 43 22 14.194%

문제

어려서부터 땅따먹기를 곧잘 즐기던 구사과는, 땅따먹기로 입신의 경지에 다다르게 되었다. 그래서 구사과는 자신만이 할 수 있는 새로운 땅따먹기 게임을 만들었는데, 이름하여 반평면 땅따먹기이다.

반평면 땅따먹기의 규칙은 땅따먹기보다 좀 더 간단하다. 땅따먹기 특이점을 넘긴 능력을 보유한 구사과는 땅따먹기에서만큼은 뭐든지 할 수 있다. 이를테면 무한히 먼 곳으로부터 손가락으로 돌을 쳐 무한히 멀리 직선으로 날아가도록 할 수 있다. 반평면 땅따먹기는 이 능력을 이용한 게임으로, 구사과가 점령하는 돌을 쳐서 날릴 때마다 그 자취인 직선을 기준으로 나뉘는 두 영역 중 (0, -∞)를 포함하는 쪽 전부를 점령하게 된다.

무한한 2차원 평면 위에서 게임을 하던 구사과는 문득 현재 자신이 점령한 땅의 모양에 관해서 궁금해졌다. 하지만 땅따먹기 이외에는 젬병인 구사과는 정작 자신이 점령한 땅에 대해서는 잘 알지 못했다. 높은 곳을 좋아하는 구사과는 종종 자신이 점령한 땅 중 해당 x좌표에서 가장 높은 y좌표가 몇인지 알고 싶었다.

우수한 프로그래머인 당신만이 구사과의 유일한 희망이다. 구사과가 게임을 진행한 정보가 주어질 때 이를 토대로 구사과의 궁굼증을 해결해주자!

입력

첫 줄에는 게임을 진행한 정보의 개수 Q(1 ≤ Q ≤ 200,000)이 주어지며, 이어서 Q 줄에 걸쳐 각 정보가 주어진다. 각 줄의 첫 번째 숫자가 1일 경우 이어서 2개의 정수 a, b(|a| ≤ 1,000,000, |b| ≤ 1,000,000,000,000)가 주어지며 이는 구사과가 y = ax + b 형태의 직선을 따라 돌을 날렸음을 의미한다. 각 줄의 첫 번째 숫자가 2일 경우 이어서 1개의 정수 x(|x| ≤ 1,000,000,000,000)이 주어지며, 이는 구사과가 현재까지 점령한 땅 중 해당 x 좌표에서 가장 높은 y값을 궁금해함을 의미한다. 첫 번째 정보는 무조건 1로 시작함이 보장된다.

출력

모든 구사과의 궁금증에 대하여 해당하는 y값을 한 줄에 걸쳐 하나씩 출력한다.

예제 입력

4
1 1 2
1 2 3
2 -100
2 100

예제 출력

-98
203

힌트

출처

Contest > Coder's High > Coder's high 2016 Round 1: Online F번