| Codeforces Round 377 (Div. 2) |
|---|
| Закончено |
Совсем скоро состоится финал чемпионата мира по программированию ICM ACPC! К сожалению, организаторы соревнования были так заняты подготовкой задач, что совершенно упустили важный технический момент — организацию электропитания рабочих мест участников.
Всего для участников выделено n компьютеров, i-й из которых имеет мощность, задающуюся целым положительным числом pi. В то же время для подключения к электросети доступно m розеток, j-я из которых предоставляет электропитание мощностью, задающейся целым положительным числом sj. Подключить i-й компьютер к j-й розетке можно тогда и только тогда, когда их мощности совпадают, то есть pi = sj, а к одной розетке можно подключить не более одного компьютера. Таким образом, если, к примеру, мощности всех компьютеров и розеток попарно различны, то ни один компьютер не представляется возможным подключить ни к одной из розеток.
Чтобы исправить ситуацию, профессор Пуч Вильямс в экстренном порядке заказал фургон переходников — делителей мощности. Каждый переходник представляет собой одну вилку и одну розетку с делителем напряжения между ними. После установки переходника на розетку мощности x, ее мощность становится равной 
, то есть делится пополам с округлением вверх, например 
и 
.
Каждый переходник можно использовать лишь единожды. На розетку можно последовательно устанавливать несколько переходников, подсоединяя их один к другому. Например, установив на розетку мощности 10 два переходника, к ней станет можно подключить компьютер мощности 3.
Организаторам предстоит установить переходники так, чтобы одновременно подключить максимальное количество компьютеров c. Если существует несколько возможных конфигураций подключения, организаторы хотят найти ту, которая использует минимальное число переходников u для подключения c компьютеров.
Помогите организаторам найти максимально возможное число компьютеров c, которые можно подключить одновременно, а также минимальное число адаптеров u, необходимых для этого.
Фургон переходников содержит достаточное их количество для выполнения задачи. Гарантируется, что получится подключить хотя бы один компьютер.
В первой строке содержится два целых числа n и m (1 ≤ n, m ≤ 200 000) — количество компьютеров и розеток соответственно.
Во второй строке содержится n целых чисел p1, p2, ..., pn (1 ≤ pi ≤ 109) — мощности, требуемые для питания компьютеров.
В третьей строке содержится m целых чисел s1, s2, ..., sm (1 ≤ si ≤ 109) — мощности, предоставляемые розетками.
В первую строку выведите два числа c и u — максимальное количество компьютеров, которые можно одновременно подключить, и минимальное количество переходников, чтобы подключить c компьютеров.
Во второй строке выведите m целых чисел a1, a2, ..., am (0 ≤ ai ≤ 109), где ai равно количеству переходников, которые следует установить на i-ю розетку. Сумма всех ai должна быть равна u.
В следующей строке выведите n целых чисел b1, b2, ..., bn (0 ≤ bi ≤ m), где bj-е равно номеру розетки, к которую следует подключить j-й компьютер. Значение bj = 0, что j-й компьютер не будет подключен к какой-либо розетке. Все bj, отличные от 0, должны быть попарно различны. Мощность j-го компьютера должна совпадать с мощностью розетки bj после установки abj переходников. Количество ненулевых bj должно быть равно c.
Если ответов несколько, выведите любой.
2 2
1 1
2 2
2 2
1 1
1 2
2 1
2 100
99
1 6
6
1 0
