{"raw_statement":[{"iden":"statement","content":"Ayoub wants to buy k boxes of apples, and there are n shops where he can buy apples from. The price of one box of apples in the ith shop equals to pi.\n\nIt is obvious that Ayoub should go to the shop with the minimal price per box. When the government saw everyone buying from the same shop, they made a special rule so that people will buy from different shops.\n\nThe cost of buying the jth apple box from the ith shop is equal to pi + (j - 1)  ×  x\n\nFor example, if the price of one box from a specific shop is 5 and x = 3. If you want to buy 3 boxes, you will pay 5 money on the first box and 5 + x on the second box, and 5 + 2 × x on the third box, in total paying 5 + 8 + 11 = 24.\n\nNow you should tell Ayoub how many boxes he should buy from every shop so that the total money he will pay is minimized.\n\nFirst line contains 3 integers n k x (1 ≤ n ≤ 105) (1 ≤ k, x ≤ 109) which are the number of shops and the number of box Ayoub wants to buy and the amount of money you should pay more after buying a box from a specific shop.\n\nSecond line contains n integers, the ith one is pi (1 ≤ pi ≤ 109) which is the price of a box of apples from the ith shop.\n\nYou should print n integers, the ith one should be the number of box Ayoub should buy from the ith shop.\n\nMake sure that the amount of money will be payed will be minimized as possible.\n\nIf there are more than one answer you can print any of them.\n\nIn the second sample Ayoub will pay 1 and 4 to the first shop and will pay 2 to the third shop and will pay 3 to the fourth shop, in total he will buy 10 money.\n\n"},{"iden":"input","content":"First line contains 3 integers n k x (1 ≤ n ≤ 105) (1 ≤ k, x ≤ 109) which are the number of shops and the number of box Ayoub wants to buy and the amount of money you should pay more after buying a box from a specific shop.Second line contains n integers, the ith one is pi (1 ≤ pi ≤ 109) which is the price of a box of apples from the ith shop."},{"iden":"output","content":"You should print n integers, the ith one should be the number of box Ayoub should buy from the ith shop.Make sure that the amount of money will be payed will be minimized as possible.If there are more than one answer you can print any of them."},{"iden":"examples","content":"Input3 2 52 2 2Output1 1 0Input4 4 31 5 2 3Output2 0 1 1"},{"iden":"note","content":"In the second sample Ayoub will pay 1 and 4 to the first shop and will pay 2 to the third shop and will pay 3 to the fourth shop, in total he will buy 10 money."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, k, x \\in \\mathbb{Z}^+ $: number of shops, total boxes to buy, and incremental cost per additional box from the same shop.  \nLet $ P = (p_1, p_2, \\dots, p_n) \\in \\mathbb{Z}^n $: price per box at each shop.  \nLet $ a_i \\in \\mathbb{Z}_{\\geq 0} $: number of boxes bought from shop $ i $, for $ i = 1, \\dots, n $.  \n\n**Constraints**  \n1. $ \\sum_{i=1}^n a_i = k $  \n2. $ a_i \\geq 0 $ for all $ i \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nMinimize total cost:  \n$$\n\\sum_{i=1}^n \\sum_{j=1}^{a_i} \\left( p_i + (j - 1) \\cdot x \\right)\n= \\sum_{i=1}^n \\left( a_i p_i + x \\cdot \\frac{a_i(a_i - 1)}{2} \\right)\n$$","simple_statement":"Ayoub wants to buy exactly k boxes of apples from n shops.  \nEach shop i has a base price p_i for one box.  \nIf you buy j boxes from shop i, the cost is:  \np_i + (0×x) for the 1st box,  \np_i + (1×x) for the 2nd box,  \np_i + (2×x) for the 3rd box,  \n...,  \np_i + ((j-1)×x) for the j-th box.  \n\nSo total cost from shop i if you buy j boxes:  \nj * p_i + x * (0 + 1 + 2 + ... + (j-1)) = j * p_i + x * j*(j-1)/2  \n\nYou must buy exactly k boxes total, and can buy any number (including zero) from each shop.  \n\nGoal: Minimize total cost.  \n\nOutput: n integers — how many boxes to buy from each shop.  \n\n(If multiple answers exist, print any.)","has_page_source":false}