Одна карточная игра, слывущая испытанием интеллекта, называется «Канг». В этой игре у каждой карты есть очки, являющиеся положительным целым числом. В начале вы получаете $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, а раздел «Описание файла грейдера» поясняет работу этого файла.