Laersh is a Pokemino trainer and he just captured his first pokemino. Throughout his journey he will capture more Pokeminos. Each Pokemino has an attack and a defense level. A Pokemino is better than another one if it has greater attack and greater defense level. Besides capturing Pokeminos, Laersh can breed any two Pokeminos that he owns and generate a new Pokemino. This new Pokemino's attack and defense will be a linear combination of its parents attributes:
Attackchild = Attackparent1 * c + Attackparent2 * (1 - c)
Defensechild = Defenseparent1 * c + Defenseparent2 * (1 - c)
The number c is the same for attack and defense, and can be any number 0 ≤ c ≤ 1.
An useless Pokemino is a Pokemino such that Laersh owns a better Pokemino, or he can breed a better Pokemino. For each new Pokemino that Laersh captures, help him figuring out the number of useless Pokeminos that he owns.
The first line of the input contains one integer N (1 ≤ N ≤ 105). N lines will follow. The i-th line will contain two integers Ai (0 ≤ Ai ≤ 109) and Di (0 ≤ Di ≤ 109) each. Ai represents the attack of Pokemino i and Di represents the defense of Pokemino i. Note: No two captured Pokeminos will have the same attack and defense.
Output N numbers, the i-th number represents how many useless Pokeminos there are when the i-th Pokemino is captured.
## Input
The first line of the input contains one integer N (1 ≤ N ≤ 105). N lines will follow. The i-th line will contain two integers Ai (0 ≤ Ai ≤ 109) and Di (0 ≤ Di ≤ 109) each. Ai represents the attack of Pokemino i and Di represents the defense of Pokemino i. Note: No two captured Pokeminos will have the same attack and defense.
## Output
Output N numbers, the i-th number represents how many useless Pokeminos there are when the i-th Pokemino is captured.
[samples]
**Definitions**
Let $ x \in \mathbb{Z} $ be a 128-bit unsigned integer representing an IPv6 address.
Let $ H = (h_1, h_2, \dots, h_8) $ be the 8-section hexadecimal representation of $ x $, where each $ h_i \in \{0, 1, \dots, 65535\} $ is a 16-bit segment (4 hex digits), obtained by splitting $ x $ into 8 contiguous 16-bit blocks from most to least significant.
Let $ \tilde{H} = (\tilde{h}_1, \dots, \tilde{h}_8) $ be the zero-stripped version of $ H $, where $ \tilde{h}_i = \text{hex}(h_i) $ with leading zeros removed (and $ \tilde{h}_i = "0" $ if $ h_i = 0 $).
**Constraints**
1. $ 0 \le x < 2^{128} $
2. Each $ h_i $ is a 16-bit segment: $ 0 \le h_i \le 65535 $
3. The double colon `::` may be used **at most once** and **only to replace a contiguous sequence of two or more zero sections** (i.e., no `::` for a single `0`).
**Objective**
Find the abbreviated representation $ A $ of $ \tilde{H} $ such that:
- `::` replaces a contiguous subsequence $ h_j, h_{j+1}, \dots, h_{j+k-1} $ where $ k \ge 2 $ and $ h_i = 0 $ for all $ i \in [j, j+k-1] $.
- Among all valid abbreviations:
(i) Minimize the number of remaining sections (i.e., maximize the length of the zero run replaced by `::`).
(ii) If tied, choose the lexicographically smallest string representation (lex order on the colon-separated hex segments with `::` treated as a single token).
Output the unique optimal abbreviation $ A $.