У Максимуса есть коллекция волшебных амулетов, каждый из которых обладает своей магической силой. Список имеющихся у него амулетов отсортирован в порядке неубывания магической силы. Вернувшись из очередного путешествия, Максимус составил список новых амулетов, предварительно отсортировав их по невозрастанию магической силы. Теперь у него два отдельных списка и он хочет объединить их в один упорядоченный по неубыанию список.
Он хочет сделать это как можно быстрее. Помогите ему отсортировать два этих списка. Максимус просит вас написать программу, которая будет работать за O(len(A)+len(B)).
Входные данные
Программа получает на вход два неубывающих списка, каждый в отдельной строке.
Выходные данные
Программа должна вывести последовательность неубывающих чисел, полученных объединением двух данных списков.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
1 5 7
2 4 4 5 |
1 2 4 4 5 5 7 |
Запрещенные операторы: sort; sorted