There is an online game with $N$ registered players. Today, which is the $10^{100}$\-th day since its launch, the developer Takahashi examined the users' login history. It turned out that the $i$\-th player logged in for $B_i$ consecutive days from Day $A_i$, where Day $1$ is the launch day, and did not log in for the other days. In other words, the $i$\-th player logged in on Day $A_i$, $A_i+1$, $\ldots$, $A_i+B_i-1$, and only on those days. For each integer $k$ such that $1\leq k\leq N$, find the number of days on which exactly $k$ players logged in.

Input is given from Standard Input in the following format: >$N$ >$A_1$ $B_1$ >$A_2$ $B_2$ >$:$ >$A_N$ $B_N$ #### Constraints - $1 \leq N \leq 2\times 10^5$ - $1 \leq A_i \leq 10^9$ - $1 \leq B_i \leq 10^9$ - All values in input are integers.

Print $N$ integers with spaces in between, as follows: >$D_1$ $D_2$ $\cdots$ $D_N$ Here, $D_i$ denotes the number of days on which exactly $k$ players logged in.

AtCoder [ABC221D]