Giải bài trực tuyến

Trịnh là một học sinh giỏi trong lớp. Dù là một học sinh khá giỏi nhưng Trịnh luôn biết cách điều chỉnh thời khóa biểu của mình để cân bằng thời gian học và thời gian chơi thể thao vì Trịnh quan điểm rằng sức khỏe và kiến thức là hai yếu tố quan trọng để trở thành một người có ích cho xã hội. Mặc dù đã lên kế hoạch chơi thể thao nhưng dạo này thời tiết khá xấu, mưa liên miên đã cản trở các dự định rèn luyện thân thể của Trịnh.
Trong một lần bị bể kế hoạch do mưa quá to và gió giật rất mạnh nên Trịnh phải ngồi nhà. Lúc rãnh rỗi, Trịnh nghĩ rằng trời mưa thì sẽ có rất nhiều kiến nên cậu đã nghĩ ra trò chơi mới lạ với những con kiến. Cậu ta lấy một đoạn dây độ dài là X và bôi một lớp đường lên sợi dây và căng ra hai đầu. Sau đó, Trịnh chợp mắt một lát trong lúc chờ đợi lũ kiến bị dụ vào. Lúc tỉnh dậy, Trịnh đã thấy kiến bu đầy đoạn dây. Một số con đang đi về đầu mút bên phải của sợi dây. Các con kiến còn lại thì đang có hướng đi về đầu mút bên trái. Vì sợi dây khá mảnh nên trường hợp hai con kiến đứng cùng một chỗ sẽ không xảy ra. Trịnh đã đánh số các con kiến trên dây từ 1 -> N THEO MỘT THỨ TỰ LỘN XỘN và ghi lại vị trí của nó cũng như hướng di chuyển. Nếu con kiến thứ i đi tới một trong 2 đầu mút của sợi dây thì ngay sau đó no sẽ bị rớt ra khỏi đoạn dây. Trịnh muốn biết thời điểm mà con kiến thứ i đi tới một trong 2 đầu mút của sợi dây. Biết rằng các con kiến đi được 1 đơn vị trong một giây và nếu hai con kiến đụng nhau, chúng sẽ lập tức đổi hướng đi. Thời điểm 0 là thời điểm vị trí và hướng đi của các con kiên giống y như dữ liệu mà Trịnh đã ghi lại. Nói cách khác, thời điểm 0 là thời điểm Trịnh tỉnh dậy.
Dữ liệu vào

Dòng đầu chứa 2 số nguyên N, X.
Dòng thứ i trong N dòng tiếp theo chứa 2 số nguyên pos, dir. Trong đó pos là khoảng cách từ con kiến thứ i tới đầu mút bên trái của sợi dây và dir là hướng di chuyển của con kiến thứ i. Biến dir mang 2 giá trị là 0 và 1 tương ứng với hướng đi sang bên trái và hướng đi sang bên phải.

Dữ liệu ra

Gồm N dòng, dòng thứ i chứa thời điểm mà con kiến thứ i đi ra khỏi sợi dây.

Ràng buộc
 

30% số test N ≤ 1000, X ≤ 1000.
30% số test N ≤ 1000, X ≤ 109.
40% số test N ≤ 106, X ≤ 109.

 
Ví dụ
Dữ liệu vào:
4 10
3 0
6 0
2 1
7 1

Dữ liệu ra:
6
8
3
3