Bài 4. Uống nước Giờ ra chơi, sân trường có N học sinh đang chơi đùa. Sau giờ ra chơi, các bạn khát nước và muốn uống nước. Chỉ có một thùng nước uống duy nhất nên mỗi thời điểm chỉ có một học sinh được sử dụng, vì vậy các học sinh phải xếp hàng để uống nước. Học sinh thứ i đến và xếp vào cuối hàng đợi vào giây thứ L[i]. Nếu có nhiều học sinh đến xếp hàng vào cùng một thời điểm, thì học sinh có chỉ số lớn hơn sẽ đến đứng sau học sinh có chỉ số nhỏ hơn. Các học sinh trong hàng đợi cư xử như sau: nếu không có ai trong hàng đợi đứng trước học sinh nào đó, thì học sinh này sẽ sử dụng bình nước trong đúng 1 giây và rời khỏi hàng đợi với cốc nước của mình; ngược lại thì học sinh này chờ người đứng trước lấy nước. Nếu đến giây thứ R[i] mà học sinh thứ i vẫn chưa đến lượt lấy nước (do có ai đó còn đứng trước bạn ấy trong hàng), thì bạn ấy sẽ rời khỏi hàng đợi mà không uống nước nữa. Với mỗi học sinh, em hãy xác định số giây mà bạn ấy sẽ sử dụng bình và lấy nước của mình (nếu bạn ấy vẫn chờ được) hoặc cho biết bạn này không chờ được đến lượt mình và đã bỏ hàng. Đầu vào Dòng đầu tiên của đầu vào chứa một số nguyên T là số bộ dữ liệu. Mỗi bộ dữ liệu gồm: • Dòng đầu chứa một số nguyên N là số lượng học sinh. • Dòng thứ i trong N dòng sau chứa hai số nguyên L[i], R[i] cho biết thời điểm học sinh thứ i vào cuối hàng đợi và thời điểm học sinh này rời khỏi hàng đợi nếu cậu ta vẫn không thể lấy được nước. Dữ liệu đảm bảo L[i - 1] ≤ L[i] (∀i = 2..N ). Hạn chế dữ liệu • 1 ≤ T, N ≤ 1000, Tổng giá trị N trong tất cả các bộ dữ liệu không vượt quá 1000. • 1 ≤ L[i] ≤ R[i] ≤ 5000, i = 1..N Đầu ra Ứng với mỗi bộ dữ liệu vào, chương trình của bạn cần in ra một dòng chứa N số nguyên, số thứ i là số giây mà học sinh thứ i lấy được nước và ra khỏi hàng, hoặc in ra 0 nếu cậu ta rời hàng mà không uống nước. Ví dụ Đầu vào 2 2 1 3 1 4 3 1 5 1 1 2 3 Đầu ra 1 2 1 0 2 Giải thích ví dụ Ví dụ trên có 2 bộ dữ liệu (T = 2): • Với bộ dữ liệu 1: Trong giây thứ 1, học sinh thứ 1 và 2 đến xếp hàng và học sinh thứ 1 được uống nước vào giây 1, học sinh thứ 2 được uống nước vào giây thứ 2. • Với bộ dữ liệu 2: Trong giây thứ 1, học sinh 1 và 2 đến xếp hàng, học sinh 1 được uống nước vào giây thứ 1 và học sinh 2 không đợi được uống nước đã bỏ hàng. Trong giây thứ 2, học sinh thứ 3 đến và uống ước vào giây thứ 2.