비탄성 충돌하는 공

무한한 수직선이 있고, 수는 왼쪽에서 오른쪽으로 커진다. 이 선 위를 몇 개의 공이 굴러간다. 처음에 각 공은 정수 좌표에 있고 질량은 1이다. 공의 크기는 무시할 수 있을 만큼 작다.

공들은 일정한 속력으로 연속해서 움직이기 시작한다. 어떤 공은 초기 속도가 $+1$이라서 단위 시간에 오른쪽으로 1만큼 움직이고, 다른 공은 초기 속도가 $-1$이라서 단위 시간에 왼쪽으로 1만큼 움직인다.

두 개 이상의 공이 같은 순간 같은 지점에서 만나면 충돌이 일어난다. 공의 충돌은 완전 비탄성이다. 즉, 만난 모든 공은 하나의 새로운 공으로 대체된다. 새 공의 질량 $m_{\mathrm{new}}$은 충돌한 모든 공의 질량의 합과 같고, 속도는 운동량 보존 법칙으로 정해진다. 충돌 후의 값 $v_{\mathrm{new}} \cdot m_{\mathrm{new}}$는 충돌한 모든 공의 값 $v_{i} \cdot m_{i}$의 합과 같다. 새 공의 크기도 여전히 무시할 수 있을 만큼 작다. 공이 연속해서 움직이므로 충돌은 정수가 아닌 시각에 일어날 수도 있다.

충돌 횟수는 유한하므로 언젠가는 충돌이 더 이상 일어나지 않는다. 모든 충돌이 끝난 뒤 선 위에 있는 공의 질량은 무엇인가? 왼쪽에서 오른쪽 순서로 나열하라.

첫째 줄에 공의 개수 $n$이 주어진다 ($1 \le n \le 300\,000$). 다음 $n$개의 줄에 각각 하나의 공이 "$x$ $v$" 형식으로 주어진다. $x$는 공의 초기 좌표, $v$는 공의 초기 속도이다. 좌표는 $0$ 이상 $10^{9}$ 이하의 정수이다. 속도는 "+1"(오른쪽으로 이동) 또는 "-1"(왼쪽으로 이동) 중 하나로 주어진다. 주어지는 좌표는 모두 다르다.

모든 충돌이 끝난 뒤 남은 공의 질량을 왼쪽에서 오른쪽 순서로 나열하여 공백으로 구분해 한 줄에 출력한다.