The executive chef is trying to bring some competitive spirit into his kitchen. He wants to split the chefs into two teams based on their age - he'll form the young and the old team. To make it fair, he will split them evenly or give the young team one person advantage when there is an odd number of chefs. Ages of all employees are unique. The executive chef also rated all chefs according to their cooking skills. Rating of a team is equal to the sum of ratings of its members. The chefs have developed a habit of coming to work late. The executive chef wants to keep the teams as fair as possible at all times and is therefore forced to change the teams each time one of the chefs comes to work in the morning. He needs your help with this task.

Input
The first line contains the number of chefs N. The following N lines describe the chefs in order as they come to work. Each chef is described by two integers, his or her age Ai and rating Ri.

Output
Every time a new chef joins the kitchen, output the absolute difference between team ratings.

Constraints

1 <= N <= 10^5
1 <= Ai <= 10^9
1 <= Ri <= 1000


Example

Input:
5
2 3
1 7
5 5
3 1
8 15

Output:
3
4
5
4
9
from heapq import *

def push_to_young(young, item):
    heappush(young, (-item[0], item[1]))

def pop_from_young(young):
    i = heappop(young)
    return (-i[0], i[1])

def push_to_old(old, item):
    heappush(old, item)

def pop_from_old(old):
    return heappop(old)

N = int(raw_input())
young = []
old = []
sum_young = 0
sum_old = 0
for _ in range(N):
    [A, R] = [int(x) for x in raw_input().rstrip().split(" ")]
    if len(young) == 0:
        push_to_young(young, (A, R))
        sum_young += R
    elif len(young) == len(old):
        if A <= old[0][0]:
            push_to_young(young, (A, R))
            sum_young += R
        else:
            x = pop_from_old(old)
            push_to_old(old, (A, R))
            push_to_young(young, x)
            sum_young += x[1]
            sum_old += R-x[1]
    else:
        if A < -young[0][0]:
            x = pop_from_young(young)
            push_to_young(young, (A, R))
            push_to_old(old, x)
            sum_old += x[1]
            sum_young += R-x[1]
        else:
            push_to_old(old, (A, R))
            sum_old += R
    #print(young)
    #print(old)
    print(abs(sum_young - sum_old))