Có ~n~ chú kiến đánh số từ 1 tới ~n~ đứng quanh một cái hồ hình tròn có chu vi ~m~ mét. Theo chiều kim đồng hồ, sau 1 mét từ chú kiến 1 là chú kiến 2, sau 1 mét từ chú kiến 2 là chú kiến 3, ..., sau 1 mét từ chú kiến ~n~ là chú kiến 1. Các chú kiến xuất phát cùng lúc, di chuyển quanh hồ với tốc độ như nhau.

Với mỗi chú kiến ~i~, ta được biết hai thông tin:

• Ký tự ~c_i~ cho biết hướng đi: ~c_i = '+'~ nếu chú kiến thứ ~i~ đi theo chiều kim đồng hồ, ~c_i = '-'~ nếu chú kiến thứ ~i~ đi ngược chiều kim đồng hồ.
• Số nguyên dương ~d_i~ cho biết độ dài quãng đường mà chú kiến thứ ~i~ sẽ đi.

Nếu hai chú kiến đi ngược chiều gặp nhau, chúng sẽ chạm râu để thực hiện lời chào rồi đi tiếp. Thời gian chào không đáng kể và không ảnh hưởng tới tốc độ cũng như hướng đi của kiến. Lưu ý rằng hai chú kiến có thể gặp và chào nhau nhiều lần. Sau khi chú kiến đi hết quãng đường đã định, nó sẽ rời khỏi vòng hồ và không thực hiện bất kỳ lời chào nào nữa.

Yêu cầu: Với mỗi chú kiến, hãy cho biết trong suốt hành trình đã có bao nhiêu lời chào được chú kiến đó thực hiện (lời chào thực hiện vào đúng thời điểm một trong hai chú kiến kết thúc hành trình cũng được tính nếu có).

Input

• Dòng 1 chứa số nguyên dương ~n~ (~n \le 2 \times 10^5~) và chu vi hồ ~m~ (~m \le 10^9~).
• ~n~ dòng tiếp theo, mỗi dòng chứa ký tự ~c_i~ và số nguyên dương ~d_i~ liền nhau (~|d_i| \le 10^9~).

Output

Ghi ra ~n~ dòng, dòng thứ ~i~ ghi một số nguyên là số lời chào mà chú kiến thứ ~i~ thực hiện trong suốt hành trình của mình.

Sample Input 1

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

Sample Output 1

5
6
5
4
5
3

Subtasks

• 30% số điểm ứng với các test có ~n, d_1, d_2, ..., d_n \le 100~.
• 30% số điểm ứng với các test có ~n \le 5000~.
• 20% số điểm ứng với các test có ~d_1 = d_2 = ... = d_n~.
• 20% số điểm ứng với các test không có ràng buộc bổ sung.