ALAKE - Hồ nhân tạo

Giới hạn
  • Thời gian: 0.09s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

 

Những ngày hè nóng nực và ngột ngạt đã đến và những chú bò đang bắt đầu kêu ca. Bác John quyết định xây một hồ nước nhân tạo. Hồ nước có thể được mô tả như 1 vùng đất 2 chiều gồm N đoạn (N <= 100 000) đánh số từ 1 đến N từ trái sang phải. Đoạn thứ i được mô tả bởi 2 số nguyên W_i (1 <= W_i <= 1000) và H_i (1 <= H_i <= 10^9 lần lượt là độ rộng và chiều cao của đoạn thứ i. Không có 2 đoạn nào có độ cao bằng nhau. 2 bức tường cao vô tận chặn ở 2 đầu trái và phải. Sau đây là 1 ví dụ về hình dạng hồ nước.

        *             *  : 
        *             *  : 
        *             *  8 
        *    ***      *  7 
        *    ***      *  6 
        *    ***      *  5 
        *    **********  4 <- độ cao 
        *    **********  3 
        ***************  2 
        ***************  1 
Đoạn    |1111222333333| 

Lúc mặt trời mọc, bác John bắt đầu đổ nước vào nơi có độ cao thấp nhất với tốc độ 1 ô vuông 1x1 trên 1 phút. Nước sẽ rơi xuống đến khi nó chạm vào đáy và chảy sang các vùng bên cạnh như thông thường

  Nước              Nước tràn 
  |                       |        
* |          *      *     |      *      *            * 
* V          *      *     V      *      *            * 
*            *      *    ....    *      *~~~~~~~~~~~~* 
*    **      *      *~~~~** :    *      *~~~~**~~~~~~* 
*    **      *      *~~~~** :    *      *~~~~**~~~~~~* 
*    **      *      *~~~~**~~~~~~*      *~~~~**~~~~~~* 
*    *********      *~~~~*********      *~~~~********* 
*~~~~*********      *~~~~*********      *~~~~********* 
**************      **************      ************** 
**************      **************      ************** 

 

  • Sau 4 phút: Đoạn 1 bị phủ

  • Sau 26 phút: Đoạn 3 bị phủ

  • Sau 50 phút: Đoạn 2 bị phủ

Input

Dòng 1: N

Dòng 2..N+1: dòng thứ i+1 gồm 2 số W_i và H_i

Output

Gồm N dòng, dòng thứ i ghi thời điểm mà đoạn thứ i bị mực nước phủ lên với độ cao 1

Example

Input:
3
1 4
1 7
1 2


Output:
6
11
1


  • Người up: huy391992
  • Nguồn bài: USACO