Когда детектив Бенуа Бланк получил конверт с деньгами и очередное анонимное письмо с предложением заняться расследованием преступления, он сразу выдвинулся на место, чтобы опросить подозреваемых.
Всего есть $$$n$$$ подозреваемых, $$$i$$$-й из которых характеризуется скучностью $$$a_i$$$. Скучность дела в каждый момент времени определяется как суммарная скучность всех свидетелей, уже давших показания.
Как известно, Бенуа Бланк терпеть не может скучные расследования. Поэтому есть $$$m$$$ «критических точек», $$$i$$$-я из которых описывается числом $$$b_i$$$: как только скучность дела становится больше $$$b_i$$$, интерес детектива к делу уменьшается на фиксированную величину.
Вы заинтересованы в том, чтобы детектив взялся за дело и довел его до конца, поэтому перед вами стоит задача расположить рассказы подозреваемых в таком порядке, при котором интерес Бенуа Бланка к делу после допроса всех подозреваемых будет максимальным.
В первой строке дано целое число $$$n$$$ — количество подозреваемых ($$$1 \leqslant n \leqslant 2 \cdot 10^5$$$). В следующей строке через пробел перечислены $$$n$$$ целых чисел $$$a_i$$$ — значения скучности подозреваемых ($$$-10^9 \leqslant a_i \leqslant 10^9$$$).
В первой строке дано целое число $$$m$$$ — количество критических точек ($$$1 \leqslant m \leqslant 2 \cdot 10^5$$$). В следующей строке через пробел перечислены $$$m$$$ целых чисел $$$b_i$$$ — значения этих критических точек ($$$0 \leqslant b_i \leqslant 10^9$$$).
В первой строке выведите целое число $$$k$$$ — минимально возможное число критических точек, которое может быть пройдено при допросе подозреваемых.
Во второй строке выведите через пробел $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ — номера свидетелей в том порядке, в котором их следует допрашивать.
Если оптимальных ответов несколько, выведите любой из них.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке | |
1 | 20 | $$$n, m \leqslant 10$$$ | первая ошибка | ||
2 | 10 | $$$a_i | lt; 0$$$ для всех $$$i$$$ | первая ошибка | |
3 | 10 | $$$a_i \geqslant 0$$$ для всех $$$i$$$ | первая ошибка | ||
4 | 25 | $$$n, m \leqslant 1000$$$ | 1 | первая ошибка | |
5 | 35 | нет | 1 – 4 | первая ошибка |
3 2 3 1 4 1 7 10 5
2 1 2 3
4 10 -10 20 -20 5 11 12 3 24 15
0 2 4 1 3