Hai Loại Thần Chú

Trong một trận đấu, người chơi dùng các câu thần chú để tấn công quái vật. Có hai loại thần chú:

• Thần chú lửa có sức mạnh $x$ gây $x$ sát thương.
• Thần chú sét có sức mạnh $y$ gây $y$ sát thương và làm tăng gấp đôi sát thương của câu thần chú được niệm ngay sau nó.

Mỗi câu thần chú chỉ được niệm đúng một lần trong trận, nhưng thứ tự niệm là tùy ý. Nếu một câu thần chú sét được niệm ngay trước một câu thần chú khác thì sát thương của câu sau bị nhân đôi (kể cả khi câu sau cũng là thần chú sét). Câu thần chú niệm cuối cùng không có câu nào phía sau, nên nếu nó là thần chú sét thì hiệu ứng nhân đôi của nó không có tác dụng.

Ban đầu người chơi không biết câu thần chú nào. Tập thần chú thay đổi $n$ lần: mỗi lần người chơi hoặc học thêm một câu thần chú mới, hoặc quên một câu đã biết. Sau mỗi lần thay đổi, hãy tính tổng sát thương lớn nhất có thể gây ra bằng tập thần chú hiện có.

Đảm bảo rằng tại mọi thời điểm, các câu thần chú mà người chơi đang biết đều có sức mạnh đôi một khác nhau.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ , số lần thay đổi.
• Mỗi dòng trong $n$ dòng tiếp theo chứa hai số nguyên $tp$ và $d$ mô tả một thay đổi:
  • $tp=0$ nghĩa là thần chú lửa, $tp=1$ nghĩa là thần chú sét.
  • Nếu $d>0$ : học câu thần chú có sức mạnh $d$ .
  • Nếu $d<0$ : quên câu thần chú có sức mạnh $-d$ (đảm bảo trước đó người chơi đã biết câu này).

Dữ liệu ra

In ra $n$ dòng, dòng thứ $i$ là tổng sát thương lớn nhất có thể gây ra sau thay đổi thứ $i$ .

Ràng buộc

• $1\le n\le 2·{10}^5$
• $0\le tp\le 1$
• $-{10}^9\le d\le {10}^9$ , $d\ne 0$
• Sau mỗi thay đổi, các sức mạnh đang biết đôi một khác nhau.

Ví dụ