Fanfan has opened a pet shelter. The shelter provides two services: taking in abandoned pets and allowing new owners to adopt these pets.

Every adopter hopes to adopt a pet they are satisfied with. Based on the adopter's requirements, Fanfan uses a special formula he invented to derive the characteristic value $a$ of the pet the adopter wishes to adopt ($a$ is a positive integer, $a < 2^{31}$). He also assigns a characteristic value to every pet currently in the shelter. This allows him to conveniently manage the entire pet adoption process. Two situations always occur at the pet shelter: either there are too many abandoned pets, or there are too many people wanting to adopt pets and too few pets.

When there are too many abandoned pets, if an adopter arrives who wishes to adopt a pet with a characteristic value of $a$, they will adopt the pet currently in the shelter whose characteristic value is closest to $a$. (No two pets can have the same characteristic value, and no two adopters can have the same desired characteristic value.) If there are two pets that satisfy the requirement—that is, there exist two pets with characteristic values $a-b$ and $a+b$—the adopter will adopt the pet with the characteristic value $a-b$.

When there are too many people wanting to adopt pets, if an abandoned pet arrives, which adopter will be able to adopt it? The adopter who can adopt it is the one whose desired pet characteristic value is closest to the pet's characteristic value. If the pet's characteristic value is $a$, and there are two adopters whose desired pet characteristic values are $a-b$ and $a+b$, the adopter with the desired value $a-b$ will successfully adopt the pet.

If an adopter adopts a pet with a characteristic value of $a$, and their own desired pet characteristic value is $b$, then the adopter's dissatisfaction level is $\text{abs}(a-b)$.

You are given the sequence of arrivals of adopters and abandoned pets at the shelter over the course of a year. Please calculate the sum of the dissatisfaction levels of all adopters who successfully adopted a pet. At the beginning of the year, there are neither pets nor adopters in the shelter.

Input

The first line contains a positive integer $n$ ($n \le 80000$), representing the total number of pets and adopters that arrive at the shelter over the year. The following $n$ lines describe the situation of pets and adopters arriving at the shelter in chronological order. Each line contains two positive integers $a$ and $b$, where $a=0$ represents a pet, $a=1$ represents an adopter, and $b$ represents the characteristic value of the pet or the desired characteristic value of the adopter. (At any given time, the shelter contains either only pets or only adopters, and the number of these pets or adopters will not exceed $10000$.)

Output

Output a single positive integer representing the sum of the dissatisfaction levels of all adopters who successfully adopted a pet, modulo $1000000$.

Examples

Input 1

5
0 2
0 4
1 3
1 2
1 5

Output 1

3

Note

$\text{abs}(3-2) + \text{abs}(2-4)=3$, the last adopter has no pet to adopt.