В городе Старая Деревня всего две улицы, и по обеим разрешено движение только в одном направлении. На перекрестке этих улиц установлен единственный в городе светофор. В любой момент времени светофор разрешает движение по одной из двух улиц, а по другой — запрещает.
Вам известен поминутный режим работы светофора. Этот режим описывается строкой $$$s$$$ длины $$$n$$$, состоящей из цифр $$$1$$$ и $$$2$$$. Если $$$s_i = 1$$$, то в течение $$$i$$$-й минуты с начала работы светофор разрешает движение по первой улице, а иначе — по второй. После $$$n$$$-й минуты светофор начинает цикл режима работы с начала, то есть, в течение $$$(n + 1)$$$-й минуты он разрешает движение по той же улице, что и в течение $$$1$$$-й, в течение $$$(n + 2)$$$-й — по той же, что и в течение $$$2$$$-й минуты, и так далее.
Вы знаете, что всего в течение дня $$$m$$$ машин подъедут к светофору. $$$i$$$-я из этих машин подъедет в момент времени $$$t_i$$$ по одной из двух улиц. Машины на каждой улице образуют очередь и ожидают разрешающего сигнала светофора. В течение одной минуты через перекресток может проехать максимум одна машина по той улице, по которой движение разрешено, и ни одной машины по другой улице.
Вам необходимо выбрать для каждой машины, по какой улице необходимо подъехать, чтобы суммарное время ожидания всех машин было минимально возможным.
Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$k$$$ ($$$1 \le k \le 1000$$$) — количество наборов входных данных. Далее следуют наборы входных данных.
Первая строка набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — период работы светофора и количество машин, соответственно.
Вторая строка содержит строку $$$s$$$ длины $$$n$$$, состоящую из цифр $$$1$$$ и $$$2$$$ — режим работы светофора.
Третья строка содержит $$$m$$$ целых чисел $$$t_1$$$, $$$t_2$$$, ..., $$$t_m$$$ ($$$0 \le t_i \le 10^5$$$) — моменты времени, в которые машины подъезжают к перекрестку. Если машины приехала в момент времени $$$x$$$, то проехать перекресток она может не раньше, чем в $$$(x + 1)$$$-ю минуту. Если несколько машин подъезжают одновременно, они выстраиваются в очередь в порядке номеров.
Гарантируется, что сумма значений $$$n$$$, а также сумма значений $$$m$$$ по всем наборам входных данных не превосходят $$$10^5$$$.
Для каждого набора входных данных выведите две строки. В первой выведите одно целое число $$$w$$$ — суммарное время ожидания всех машин в оптимальном решении.
Во второй строке выведите $$$m$$$ целых чисел $$$s_1$$$, $$$s_2$$$, ..., $$$s_m$$$, где $$$s_i = 1$$$, если $$$i$$$-я машина должна подъехать по первой дороге, и $$$2$$$ иначе. Если существует несколько решений, выведите любое из них.
В тестах суммарной стоимостью не менее 16 баллов дополнительно выполняется: сумма значений $$$n$$$, сумма значений $$$m$$$ во всех наборах входных данных не превосходят $$$20$$$; $$$t_i \le 20$$$.
В тестах суммарной стоимостью не менее 36 баллов дополнительно выполняется: сумма значений $$$n$$$, сумма значений $$$m$$$ во всех наборах входных данных не превосходят $$$300$$$; $$$t_i \le 300$$$.
В тестах суммарной стоимостью не менее 56 баллов дополнительно выполняется: сумма значений $$$n$$$, сумма значений $$$m$$$ во всех наборах входных данных не превосходят $$$5000$$$.
33 51210 0 5 2 41 420 0 0 06 62221110 0 2 2 1 1
1 1 2 1 1 2 6 2 2 2 2 9 2 2 1 1 2 1
В первом примере ожидать зеленого сигнала будет только вторая машина в течение одной минуты, остальные проедут перекресток без остановки.
Во втором примере светофор всегда запрещает проезд по первой дороге, поэтому все машины необходимо отправить по второй дороге. Машины будут ожидать соответственно $$$0$$$, $$$1$$$, $$$2$$$ и $$$3$$$ минуты в очереди.
| Название |
|---|