Sharif Суперкомпьютер
SSC — это суперкомпьютер, разработанный в Шарифском университете, который оснащен 2 "мастер" и n "рабов" процессорами. Он способен параллельно запускать программное обеспечение: один из мастер-процессоров загружает программное обеспечение на рабов-процессоры, обеспечивая сбалансированное использование памяти и процессора, в то время как другой мастер отвечает за мониторинг системы.
Из-за зависимостей между различными частями программного обеспечения процессоры должны обмениваться большим количеством сообщений. Чтобы минимизировать накладные расходы на передачу сообщений, необходима очень быстрая сеть. Для оптимизации сети будет построена структура клики, в которой между каждой парой процессоров проложен прямой кабель связи.
Существует два типа кабелей: синие кабели, которые могут передавать до 100 мегабит в секунду, и красные кабели, которые могут передавать до 1 гигабит в секунду. Каждая пара рабов-процессоров соединена одним синим кабелем. Из-за большего объема связи между мастер-процессорами, два мастера соединены одним красным кабелем, и также каждый мастер соединен с каждым рабом другим красным кабелем.
Таким образом, SSC состоит из n+2 материнских плат, каждая из которых содержит ровно один процессор, необходимую память и n+1 одинаковых сетевых разъемов, установленных в горизонтальный ряд. Материнские платы размещены в вертикальной стойке, каждая на отдельной горизонтальной полке. Таким образом, каждая материнская плата уникально идентифицируется по своей высоте в стойке.
Система охлаждения требует, чтобы две мастер-материнские платы были размещены на самой нижней и самой верхней полках стойки. Мы предполагаем, что мастер внизу имеет высоту 0, а высоты остальных материнских плат — это целые числа, превышающие 0. Ваша задача как инженера по компьютерам — выполнить окончательную сборку SSC. Вам предоставляется пустая стойка и готовые материнские платы, и ваша задача — определить, можете ли вы разместить платы в стойке, удовлетворяющей ограничениям и длинам кабелей.
Имеется ровно 2n+1 красных кабелей с заданными размерами. Однако синие кабели доступны в m различных размерах, и у нас есть неограниченное количество кабелей каждого размера. Вы стремитесь к тому, чтобы кабели между процессорами были аккуратными и плотными, поэтому хотите установить материнские платы на таких высотах, чтобы размер кабеля, используемого между каждой парой материнских плат, точно соответствовал разнице между высотами двух плат.
Входные данные
Вход содержит несколько тестовых случаев. Первая строка каждого тестового случая содержит два числа n (1 ≤ n ≤ 100) и m (1 ≤ m ≤ 1000). Вторая строка содержит 2n+1 целых чисел, которые являются размерами кабелей Gigabit Ethernet. Третья строка содержит m целых чисел, которые являются размерами групп кабелей Megabit Ethernet. Последняя строка входа содержит два нуля.
Выходные данные
Для каждого набора данных вы должны написать n+1 целых чисел, представляющих высоты материнских плат в стойке SSC. Первое число обозначает высоту верхнего мастер-процессора, а оставшиеся n чисел — это позиции рабов в порядке возрастания. Если существует несколько решений, выберите то, которое имеет минимальный алфавитный порядок. Если решения нет, напишите "Impossible".