Gats and the Taller Landing

Time limit: 2000 msMemory limit: 256 MB

Gats is practicing jumps on a rooted tree of scratching posts. The posts are numbered $1, 2, \ldots, N$ , and post $1$ is the root. The depth of post $1$ is $0$ .

Each post $i$ has a height $H_i$ and a spring wish $S_i$ .

If Gats is currently at post $x$ , he looks only at proper ancestors of $x$ . A post $y$ is a valid landing post if $y$ is an ancestor of $x$ and

$H_y \ge H_x + S_x.$

If at least one valid landing post exists, Gats jumps to the valid landing post with maximum depth, that is, the nearest valid landing post above $x$ . If no valid landing post exists, Gats stops.

For every starting post $i$ , determine how many jumps Gats makes before stopping.

Input

The first line contains an integer $N$ ( $1 \le N \le 2 \times 10^5$ ), the number of scratching posts.

The next $N$ lines describe the posts. The -th of these lines contains two integers and (, ), the height and spring wish of post .

Output

Print $N$ integers $A_1, A_2, \ldots, A_N$ on one line, where is the number of jumps Gats makes before stopping when he starts at post .

Samples

Sample 1

Input

Output

0 1 1 2 1

From post $4$ , Gats first jumps to post $3$ , then to post $1$ , so $A_4 = 2$ . From post , only post is a valid landing post, so .

Gats and the Taller Landing

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2