Одна карткова гра, яку називають випробуванням інтелекту, має назву «Канг». У цій грі кожна карта має очки, що є додатним цілим числом. На початку ви отримуєте $N$ карт у руку, а ще $M$ карт лежать відкритими на столі в ряд зліва направо; при цьому ви бачите очки всіх карт — як отриманих у руку, так і тих, що лежать на столі. Потім ви можете добирати карти зі столу ще протягом $k$ раундів, беручи по одній карті поспіль зліва направо. Після взяття карти в кожному раунді ви можете 1 раз скинути карти з руки — будь-яку кількість карт у руці, що мають однакові очки. Вам потрібно спланувати гру так, щоб після взяття карт зі столу та скидання карт з руки за всі $k$ раундів карти, що залишилися в руці, мали найменшу суму очок.

Розглянемо такий приклад:

Якщо на початку ви маєте п'ять карт з очками $6, 3, 9, 6, 3$, а карти на столі зліва направо мають очки $4, 6, 9, 6$:

Випадок $k = 1$: якщо ви можете взяти зі столу лише 1 карту, то коли ви берете першу карту, очки ваших карт стануть такими: $6, 3, 9, 6, 3, 4$. Потім ви можете 1 раз вибрати та скинути карти з однаковими очками. Найкращий спосіб — вибрати й скинути 2 карти з очками, що дорівнюють $6$, щоб сума очок карт, які залишилися, була найменшою і дорівнювала $3 + 9 + 3 + 4 = 19$.

Випадок $k = 2$: якщо ви можете взяти зі столу 2 карти, найкращий спосіб такий: після взяття першої карти з очками, що дорівнюють $4$, ви вибираєте скинути одну карту з очками, що дорівнюють $9$. Карти, які залишилися в руці, мають очки $6, 3, 6, 3, 4$. Потім, коли ви берете 2-гу карту з очками, що дорівнюють $6$, ви зможете скинути 3 карти з очками, що дорівнюють $6$, завдяки чому сума очок решти карт стане найменшою і дорівнюватиме $3 + 3 + 4 = 10$.

Випадок $k = 3$: якщо ви можете взяти зі столу 3 карти, найкращий спосіб такий: коли ви берете першу карту, очки карт у руці стануть $6, 3, 9, 6, 3, 4$. Потім можна 1 раз вибрати карти з однаковими очками для скидання, і найкращий спосіб — скинути обидві (2) карти з очками, що дорівнюють $3$, після чого в руці залишаться карти $6, 9, 6, 4$. Далі, коли ви берете 2-гу карту з очками, що дорівнюють $6$, ви зможете скинути 3 карти з очками, що дорівнюють $6$, і в руці залишаться карти $9, 4$. А коли ви в 3-й раз берете карту з очками, що дорівнюють $9$, ви зможете скинути обидві (2) карти з очками, що дорівнюють $9$, у результаті чого сума очок карт, що залишилися, стане рівною $4$.

Випадок $k = 4$: якщо ви можете взяти зі столу 4 карти, найкращий спосіб такий: після взяття першої карти з очками, що дорівнюють $4$, виберіть скинути одну карту з очками, що дорівнюють $4$, залишивши в руці карти з очками $6, 3, 9, 6, 3$. Потім під час 2-го взяття карта має очки, що дорівнюють $6$; найкращий спосіб — скинути обидві (2) карти з очками, що дорівнюють $3$, тоді в руці залишаться карти $6, 9, 6, 6$. Під час 3-го взяття карта має очки, що дорівнюють $9$; виберіть скинути обидві (2) карти з очками, що дорівнюють $9$. Нарешті, під час взяття останньої карти з очками, що дорівнюють $6$, ви зможете скинути 4 карти з очками, що дорівнюють $6$. Унаслідок цього скидання в руці не залишиться карт, а отже, сума очок карт дорівнює $0$.

Ваше завдання (Your Task)

Знайдіть «найменшу суму очок карт, що залишилися в руці» після завершення $k$ раундів, коли $k = 1, 2, 3, \ldots, M$.

Ця задача має нестандартний формат написання програми, який використовується на реальному змаганні. Будь ласка, перегляньте кінець умови цієї задачі щодо правил використання.

Деталі реалізації

Вам необхідно реалізувати таку функцію:

std::vector<long long> capsize(std::vector<int> A, std::vector<int> B)

із такими параметрами:

• $A$ — масив довжини $N$, що задає номери карт у руці на початку.
• $B$ — масив довжини $M$, що задає номери карт, які лежать на столі, за порядком зліва направо.
• Функція повинна повернути масив $C$ довжини $M$, що представляє найменшу можливу суму очок карт у руці після $k$ раундів, коли $k = 1, 2, 3, \ldots, M$.

Наприклад, якщо $A = [6, 3, 9, 6, 3]$ і $B = [4, 6, 9, 6]$, функція повинна повернути масив $[19, 10, 4, 0]$.

Обмеження

• $1 \le N, M \le 10^6$
• $1 \le A[i] \le 10^9$ для кожного $i$, де $1 \le i \le N$
• $1 \le B[i] \le 10^9$ для кожного $i$, де $1 \le i \le M$

Підзадачі

Примітки

Поради щодо написання програми

Для цієї задачі спосіб написання програми та подання її до системи оцінювання (Grader) відрізняється від загального формату програмування, де учасник має писати частину зчитування вхідних даних і частину виведення результату. У цій задачі учасник повинен написати лише необхідну обчислювальну частину всередині заданої функції. Вхідні дані будуть доступні через параметри функції, а результати обчислень також мають повертатися через функцію, тож учаснику не потрібно писати частину зчитування вхідних даних і частину виведення.

Учасник отримає кілька таких файлів; учасник повинен змінити лише один визначений умовою файл і надіслати цей файл до системи:

• grader.cpp — основний файл, який відповідає за зчитування вхідних даних і виведення результатів.
• kang.cpp — файл, у якому учасник повинен написати обчислення програми і який учасник надсилає до системи (у файлі kang.cpp заборонено мати функцію main(), але можуть бути інші функції).
• run_cpp.sh — файл, який учасник може викликати для запуску всієї програми.
• compile_cpp.sh — файл, який учасник може викликати для компіляції програми.

Учасник отримає файл .zip, який можна завантажити із системи; після його розпакування (extract) всередині будуть усі 4 файли. Учаснику слід використовувати текстовий редактор або IDE для редагування файлу kang.cpp, а компіляцію чи запуск програми виконувати через виклик compile_cpp.sh або run_cpp.sh.

Коли учасник викликає файл run_cpp.sh для запуску програми, програма працюватиме відповідно до того, як зазначено у файлі grader.cpp, а розділ «Опис файлу грейдера» пояснює роботу цього файлу.