На відміну від Лицарів Круглого Столу, Лицарі Багатокутного Столу не виділяються благородством і з радістю вб'ють один іншого. Проте, кожний лицар володіє своєю силою, і один лицар може вбити іншого тільки якщо його сила більша, ніж сила жертви. Проте, навіть такого лицаря буде мучити совість, тому лицар може вбити максимум k інших людей.

Також, у кожного лицаря є певна кількість монет. При вбивстві лицар може забрати монети своєї жертви.

Кожний лицар задумався: а яка найбільша кількість монет може в нього бути, якщо вбивати інших лицарів буде тільки він.

Вам необхідно відповісти на це питання для кожного лицаря.

Вхідні дані:

Перший рядок містить два числа n і k (1 ≤ n ≤ 105, 0 ≤ k ≤ min(n-1, 30)) – кількість лицарів і число k, описане в умові.

В другому рядку знаходиться n чисел p[1, p2 … pn (1 ≤ pi≤ 109) – сили лицарів. Всі p_i різні.

В третьому рядку знаходиться n чисел c1, c2 … cn (1 ≤ ci ≤ 109) – кількість монет у лицарів.

Вихідні дані:

Виведіть n чисел – найбільшу кількість монет у кожного лицаря.