You have a long list of tasks that you need to do today. To accomplish task i you need Mi minutes, and the deadline for this task is Di. You need not complete a task at a stretch. You can complete a part of it, switch to another task, and then switch back.

You've realized that it might not be possible to complete all the tasks by their deadline. So you decide to do them in such a manner that the maximum amount by which a task's completion time overshoots its deadline is minimized.

Input Format

The first line contains the number of tasks, T. Each of the next T lines contains two integers, Di and Mi.

Output Format

T lines. The ith line contains the value of the maximum amount by which a task's completion time overshoots its deadline, when the first i tasks on your list are scheduled optimally.

Constraints

1≤T≤10^5

1≤Di≤10^5

1≤Mi≤10^3

SAMPLE INPUT
5
2 2
1 1
4 3
10 1
2 1

SAMPLE OUTPUT
0  
1  
2  
2  
3
import sys
import math

stdin = sys.stdin

Mid= lambda x : ((x[0] + x[1])>>1)
Lowbit = lambda x : (x&(-x))


used = {}

class Task:
    def __init__(self , _d , _m , _index):
        self.d = int(_d)
        self.m = int(_m)
        self.index = int(_index)
    def __lt__(self , other):
        if (self.d == other.d):
            return self.m > other.m
        else:
            return self.d < other.d
    def __repr__(self):
        return str((self.d , self.m))
class Node:
    def __init__(self):
        self.val = 0
        self.idx = 0
        self.add = 0
        self.cover = (0 , 0)
        self.lChild = None
        self.rChild = None
    def __lt__(self , other):
        if (self.idx not in used):
            return True
        if (other.idx not in used):
            return False
        return self.val < other.val
    def __repr__(self):
        return str(self.val)
    def build(self , cover):
        self.cover = cover
        self.idx = cover[0]
        if (cover[0] == cover[1]):
            return
        mid = Mid(cover)
        self.lChild = Node()
        self.rChild = Node()
        self.lChild.build( (cover[0] , mid) )
        self.rChild.build( (mid + 1 , cover[1]) )
    def addDown(self):
		#try
        self.lChild.addValue(self.add)
        self.rChild.addValue(self.add)
        self.add = 0
    def addValue(self , add):
        self.val += add
        self.add += add
        
    def update(self , cover, add):
        if (cover[0] <= self.cover[0] and cover[1] >= self.cover[1]):
            self.addValue(add)
            return
        if (self.add):
            self.addDown()
        mid = Mid(self.cover)
        if (cover[0] <= mid):
            self.lChild.update(cover , add)
        if (cover[1] > mid):
            self.rChild.update(cover , add)

        ret = max( self.lChild , self.rChild )
        self.val = ret.val
        self.idx = ret.idx

    def query(self , cover):
        if (cover[0] == self.cover[0] and cover[1] == self.cover[1]):
            return self
        if (self.add):
            self.addDown()
        mid = Mid(self.cover)
        if (cover[1] <= mid):
            return self.lChild.query(cover)
        elif (cover[0] > mid):
            return self.rChild.query(cover)
        else:
            vl = self.lChild.query( (cover[0] , mid) )
            vr = self.rChild.query( (mid + 1 , cover[1]) )
            return max(vl , vr)

class BinIdxTree:
    def __init__(self , size):
        self.S = [0 for i in range(size+10)]
    def add(self , x , c):
       
        while (x <= n):
            self.S[x] += c
            x += Lowbit(x)
    def getsum(self , x):
        res = 0
        while (x > 0):
            res += self.S[x]
            x -= Lowbit(x)
        return res
        
       
line = stdin.readline()
n = int(line)

segTreeRoot = Node()
segTreeRoot.build((1 , n))
bTree = BinIdxTree(n)
##try
taskList = []
rank = [0 for i in range(n+1)]

for i in range(n):
    line = stdin.readline()
    [d , m] = [int(x) for x in line.split()]
    t = Task(d , m , i)
    taskList.append(t)

taskList.sort()

for i in range(n):
    rank[ taskList[i].index ] = i

ans = 0
for i in range(n):
    p = rank[i] + 1
    bTree.add(p , taskList[p-1].m)
    used[p] = True
    segTreeRoot.update((p , p) ,  - taskList[p-1].d)
    segTreeRoot.update((p , n) , taskList[p-1].m)
    res = bTree.getsum(p) - taskList[p-1].d
    res = 0 if res < 0 else res
    if (p + 1 <= n):
        resNode = segTreeRoot.query((p + 1 , n))
        p = resNode.idx
        if (p in used):
            s =bTree.getsum(p) - taskList[p-1].d
            res = s if s > res else res
    ans = res if res > ans else ans
    print ans