로봇과 함께하는 실크로드

고대 실크로드의 일부는 카자흐스탄 남부를 지나갔다. 당신은 독자적인 특징을 가진 현대판 실크로드를 꿈꿔 왔다. 이 환상의 길 위에는 로봇과 텡게(카자흐스탄의 화폐)를 쌓아 둔 상점이 놓여 있다. 로봇이 상점이 있는 위치로 이동하면, 로봇은 그 상점의 텡게를 전부 모아 당신에게 가져다준다.

로봇은 1미터를 움직일 때마다 1텡게의 비용이 든다. 따라서 로봇을 상점까지 보내 얻는 이익은 상점에 있는 텡게 수에서 로봇이 상점에 도달하기까지 이동한 거리(미터)를 뺀 값이다.

이 상황은 여러 날에 걸쳐 진행된다. 처음에는 길에 로봇도 상점도 없다. 매일 새 로봇이나 새 상점 중 하나가 길 위의 빈 위치에 놓인다. 그 직전에 길 위의 기존 상점마다 텡게를 다시 채워서, 총액이 처음 길에 놓였을 때와 같아지게 한다. 로봇은 모두 원래의 출발 위치로 돌아간다.

매일 상점에서 텡게를 모아 얻을 수 있는 최대 이익을 구해야 한다. 같은 위치에서 출발하는 로봇은 없지만, 이동 중에는 같은 위치에 함께 있을 수 있다. 각 상점은 하루에 한 번만 텡게를 비울 수 있다.

첫째 줄에 날짜 수 $n$ ($1 ≤ n ≤ 2 \cdot 10^5$)이 주어진다. 이어서 $n$개의 줄이 주어지며, $i$번째 줄은 정수 $t_i$로 시작한다. $t_i$가 1이면 $i$일에 새 로봇이 추가되고, 2이면 새 상점이 추가된다. 그다음 정수 $x_i$ ($0 ≤ x_i ≤ 10^8$)가 주어지며, 새 로봇이나 새 상점의 위치를 나타낸다. $t_i = 2$이면 같은 줄에 정수 $c_i$ ($0 ≤ c_i ≤ 10^8$)가 하나 더 주어지며, 이는 상점에 있는 텡게 수이다. 주어지는 모든 위치는 서로 다르다.

$n$개의 정수를 출력한다. $i$번째 정수는 $i$일 이후에 얻을 수 있는 최대 이익이다.