Kỵ sĩ vàng

Trong một giải đấu có \(n\) kỵ sĩ, kỵ sĩ thứ \(i\) có sức mạnh \(p_i\) và đang giữ \(c_i\) đồng vàng. Khi hai kỵ sĩ giao đấu, kỵ sĩ thắng khi và chỉ khi sức mạnh của anh ta lớn hơn hẳn sức mạnh của đối thủ (nếu bằng nhau thì không ai thắng được ai). Người thắng lấy toàn bộ số vàng mà đối thủ đang giữ ban đầu (số vàng cướp được không được tính lại cho các trận sau của đối thủ; mỗi trận chỉ tính \(c\) ban đầu của đối phương).

Theo luật của nhà vua, mỗi kỵ sĩ chỉ được giao đấu với tối đa \(k\) kỵ sĩ khác, và mỗi kỵ sĩ có thể tự chọn đấu với ai. Với từng kỵ sĩ, hãy tính số vàng nhiều nhất mà anh ta có thể sở hữu (gồm vàng ban đầu của mình và vàng thu được) khi mỗi kỵ sĩ được xét độc lập với nhau.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\).
• Dòng thứ hai chứa \(n\) số nguyên \(p_1, p_2, \dots, p_n\).
• Dòng thứ ba chứa \(n\) số nguyên \(c_1, c_2, \dots, c_n\).

Output

In ra một dòng gồm \(n\) số nguyên cách nhau bởi dấu cách, số thứ \(i\) là lượng vàng lớn nhất mà kỵ sĩ thứ \(i\) có thể có.

Constraints

• \(1 \le n \le 10^5\), \(0 \le k \le \min(n-1, 50)\)
• \(1 \le p_i \le 10^9\)
• \(0 \le c_i \le 10^9\)

Sample Input 1

5 2
10 3 7 8 12
4 9 1 6 20

Sample Output 1

19 9 10 16 35

Explanation

• Kỵ sĩ 2 (sức mạnh \(3\)) không thắng được ai nên giữ \(9\).
• Kỵ sĩ 3 (sức mạnh \(7\)) chỉ thắng được kỵ sĩ 2: \(1 + 9 = 10\).
• Kỵ sĩ 4 (sức mạnh \(8\)) thắng được kỵ sĩ 2 và 3, lấy cả hai: \(6 + 9 + 1 = 16\).
• Kỵ sĩ 1 (sức mạnh \(10\)) thắng được kỵ sĩ 2, 3, 4 nhưng chỉ được đấu \(2\) trận nên chọn kỵ sĩ 2 và 4: \(4 + 9 + 6 = 19\).
• Kỵ sĩ 5 (sức mạnh \(12\)) thắng cả bốn người, chọn hai người giàu nhất (kỵ sĩ 2 và 4): \(20 + 9 + 6 = 35\).