Knights of the Polygonal Table
The Knights of the Polygonal Table, unlike their Round Table counterparts, are not bound by nobility and are willing to eliminate each other. Each knight has a unique strength, and one can only defeat another if his strength surpasses that of his opponent. However, even the strongest knight is limited by his conscience and can kill at most k other knights.
Moreover, each knight possesses a certain number of coins. When a knight kills another, he acquires all the coins of his victim.
Each knight is curious: what is the maximum number of coins he can accumulate if he is the sole knight doing the killing?
Your task is to determine this maximum for each knight.
Input
The first line contains two integers n and k (1 ≤ n ≤ 10^5, 0 ≤ k ≤ min(n-1, 30)) – representing the number of knights and the maximum number of knights a single knight can kill, respectively.
The second line lists n integers p[1], p[2], …, p[n] (1 ≤ p[i] ≤ 10^9) – the strengths of the knights, with all strengths being distinct.
The third line lists n integers c[1], c[2], …, c[n] (1 ≤ c[i] ≤ 10^9) – the number of coins each knight initially possesses.
Output
Output n integers – the maximum number of coins each knight can have.