Có ~n~ chú kiến đứng quanh một hồ hình tròn chu vi ~n~ mét. Theo chiều kim đồng hồ, kiến thứ ~i+1~ đứng cách kiến thứ ~i~ đúng ~1~ mét. Mỗi kiến có hướng đi ~c_i~, trong đó ~c_i=+~ là đi theo chiều kim đồng hồ và ~c_i=-~ là đi ngược chiều kim đồng hồ. Kiến thứ ~i~ đi tổng cộng ~d_i~ mét rồi rời khỏi vòng hồ.

Khi hai kiến đi ngược chiều gặp nhau, chúng chào nhau rồi tiếp tục đi. Một cặp kiến có thể gặp nhau nhiều lần. Lời chào tại đúng thời điểm một trong hai kiến kết thúc hành trình vẫn được tính.

Với mỗi kiến, hãy đếm số lời chào mà kiến đó thực hiện.

Input

Dòng đầu chứa số nguyên dương ~n~.

~n~ dòng tiếp theo, dòng thứ ~i~ chứa ký tự ~c_i~ và số nguyên dương ~d_i~ viết liền nhau.

Output

In ra ~n~ dòng, dòng thứ ~i~ là số lời chào của kiến thứ ~i~.

Subtask

• 30% số điểm: ~n,d_i \le 100~.
• 30% số điểm: ~n \le 5000~.
• 20% số điểm: ~d_1=d_2=\cdots=d_n~.
• 20% số điểm: ~n \le 2\cdot 10^5~, ~d_i \le 10^9~.

Ví dụ

6
+4
-5
-5
+5
+5
-3

5
6
5
4
5
3