An auction house is cataloguing n lots for its next sale, numbered 0 to n - 1. Each lot i has been assigned an authentication tier tier[i] (lower tiers indicate earlier, less-scrutinized provenance) and an appraised value value[i].

To help buyers judge how a lot compares against less-authenticated lots, the house computes a rarity credit for every lot: the rarity credit of lot i is the sum of the k largest appraised values among all lots whose authentication tier is strictly less than tier[i]. If fewer than k such lots exist, sum all of them; if none exist, the rarity credit is 0.

Compute the rarity credit of every lot.

Input format

• Line 1: two integers n and k.
• Line 2: n integers, tier[0], tier[1], ..., tier[n-1].
• Line 3: n integers, value[0], value[1], ..., value[n-1].

Output format

Print n integers separated by single spaces: the rarity credit of lot 0, lot 1, ..., lot n - 1, in that order.

Constraints

• 1 <= n <= 10^5
• 1 <= k <= n
• 1 <= tier[i] <= 10^9
• 0 <= value[i] <= 10^9

4 2
2 1 1 3
10 20 30 5

50 0 0 50

1 1
5
100

0