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 \leq 10^5~) đá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 \leq W_i \leq 10^3~) và ~H_i~ (~1 \le H_i \leq 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~.

Sample Input

3
1 4
1 7
1 2

Sample Output

6
11
1