Place Ads Into the Shortest Column

Problem: Place Ads Into the Currently Shortest Column You are given a sequence of ads, where each ad has a height. There are k columns, numbered from 0 to k - 1 from left to right. Process the ads in the given order. For each ad: Place it into the column with the smallest current total height. If multiple columns have the same smallest height, choose the smallest column index, i.e. the leftmost column. After placing the ad, that column's total height increases by the ad's height. Return: The column index chosen for each ad. The final height of every column after all ads are placed. The original version uses k = 2; the follow-up generalizes it to arbitrary k columns. Input Format n k h1 h2 ... hn n is the number of ads. k is the number of columns. hi is the height of the i-th ad. Output Format Print two lines: The first line contains n integers, where the i-th integer is the column index chosen for the i-th ad. The second line contains k integers, representing the final height of each column. Constraints 0 <= n <= 2 * 10^5 1 <= k <= 2 * 10^5 1 <= hi <= 10^9 Example Input: 5 2 3 1 4 2 2 Output: 0 1 1 0 0 7 5 Explanation: Initial heights are [0, 0]. Tie, choose column 0, place height 3, heights become [3, 0]. Place height 1 into column 1, heights become [3, 1]. Place height 4 into column 1, heights become [3, 5]. Place height 2 into column 0, heights become [5, 5]. Tie, choose column 0, place height 2, heights become [7, 5]. Example Input 5 2 3 1 4 2 2 Output 0 1 1 0 0 7 5