{"raw_statement":[{"iden":"statement","content":"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:\n\nAttackchild = Attackparent1 * c + Attackparent2 * (1 - c)\n\nDefensechild = Defenseparent1 * c + Defenseparent2 * (1 - c)\n\nThe number c is the same for attack and defense, and can be any number 0 ≤ c ≤ 1.\n\nAn 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. \n\nThe 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.\n\nOutput N numbers, the i-th number represents how many useless Pokeminos there are when the i-th Pokemino is captured.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"Output N numbers, the i-th number represents how many useless Pokeminos there are when the i-th Pokemino is captured."},{"iden":"examples","content":"Input1010 010 110 29 38 47 43 42 41 40 4Output0000000000Input53 66 46 97 210 8Output00123"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ x \\in \\mathbb{Z} $ be a 128-bit unsigned integer representing an IPv6 address.  \nLet $ 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.  \nLet $ \\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 $).\n\n**Constraints**  \n1. $ 0 \\le x < 2^{128} $  \n2. Each $ h_i $ is a 16-bit segment: $ 0 \\le h_i \\le 65535 $  \n3. 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`).  \n\n**Objective**  \nFind the abbreviated representation $ A $ of $ \\tilde{H} $ such that:  \n- `::` 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] $.  \n- Among all valid abbreviations:  \n  (i) Minimize the number of remaining sections (i.e., maximize the length of the zero run replaced by `::`).  \n  (ii) If tied, choose the lexicographically smallest string representation (lex order on the colon-separated hex segments with `::` treated as a single token).  \n\nOutput the unique optimal abbreviation $ A $.","simple_statement":"Given a 128-bit IPv6 address as a decimal number, convert it to hexadecimal, split into 8 groups of 4 hex digits, remove leading zeros, and abbreviate the longest consecutive group of zeros with \"::\". If multiple abbreviations exist, choose the one with fewest sections, and if tied, pick lexicographically smallest.","has_page_source":false}