На відміну від Рицарів Круглого Столу, Рицарі Багатокутного Столу не виділяються благородством і з радістю вб'ють один іншого. Проте, кожний рицар володіє своєю силою, і один рицар може вбити іншого тільки якщо його сила більша, ніж сила жертви. Проте, навіть такого рицаря буде мучити совість, тому рицар може вбити максимум k інших людей.
Також, у кожного рицаря є певна кількість монет. При вбивстві рицар може забрати монети своєї жертви.
Кожний рицар задумався: а яка найбільша кількість монет може в нього бути, якщо вбивати інших рицарів буде тільки він.
Вам необхідно відповісти на це питання для кожного рицаря.
Перший рядок містить два числа n і k (1 ≤ n ≤ 10^5
, 0 ≤ k ≤ min(n-1, 30)) – кількість рицарів і число k, описане в умові.
В другому рядку знаходиться n чисел p[1
, p[2]
… p[n]
(1 ≤ p[i]
≤ 10^9
) – сили рицарів. Всі p_i різні.
В третьому рядку знаходиться n чисел c[1]
, c[2]
… c[n]
(1 ≤ c[i]
≤ 10^9
) – кількість монет у рицарів.
Виведіть n чисел – найбільшу кількість монет у кожного рицаря.