Tariffs
A mobile operator has decided to create several unlimited tariff plans, each with different monthly subscription fees and additional services. The company's customer relationship managers have determined how much each VIP subscriber is willing to spend on mobile services per month. The company now wants to offer each subscriber a personalized tariff plan. However, due to antitrust regulations, the company is limited to offering no more than K unlimited tariff plans.
Your task is to assist the company's managers in developing these K tariff plans to maximize the company's profits.
Input
The first line of the input contains two numbers: the number of VIP subscribers N (1 ≤ N ≤ 100) and the number of tariff plans K (1 ≤ K ≤ 100). Following this, N integers A_i are provided, representing the amount each i-th subscriber is willing to spend on communication per month (0 ≤ A_i ≤ 100000).
Output
Output K natural numbers, representing the subscription fees for the tariff plans in ascending order. Each subscription fee must be at least 1 and cannot exceed 10^9.
Each subscriber will be offered a tariff plan with the highest possible subscription fee that does not exceed A_i. If no suitable tariff plan is available, the subscriber will not be serviced by the company.
The company's profit is calculated as the sum of the subscription fees paid by all subscribers.
Comments on examples
Example 1: The subscriber willing to pay 1 will not be serviced. The subscriber willing to pay 4 will be connected to the first tariff plan. Those willing to pay 5 will be connected to the second plan, those willing to pay 8 and 9 to the third, and the one willing to pay 80 to the fourth. The total profit will be 4 + 5*4 + 8*2 + 80 = 120.
Example 2: Each subscriber is connected to their own tariff, with the 4th tariff unused. Total profit is 1+2+30=33.
Example 3: All subscribers except the first and third are connected to a single tariff. Total profit is 4*4 = 16.
Example 4: Since a tariff with a zero subscription fee is not allowed, the 1st and 3rd subscribers will not be serviced.