Слияние двух упорядоченных последовательностей чисел в одну упорядоченную основная идея сортировки слиянием. Эта сортировка работает быстро, а слияние двух упорядоченных после-
довательностей легко выполняется в том числе и человеком вручную.
В этой задаче по полученной в результате слияния неубывающей последовательности чисел вам предстоит восстановить две исходных неубывающих последовательности одинакового размера.
Некоторые числа в исходных последовательностях известны, а некоторые заменены знаком "?".
Результат слияния известен полностью. Вам необходимо подставить на место знаков вопроса числа так, чтобы исходные последовательности были неубывающими и при слиянии образовывали заданную результирующую последовательность.
Входные данные
В первой входного файла строке содержится число N количество элементов в каждой из исходных последовательностей. Во второй и третьей строках записано по N чисел и знаков вопроса
содержимое первой и второй последовательности соответственно. В четвертой строке записано 2хN чисел - результат слияния.
Выходные данные
Вывод должен содержать 2 строки по N чисел в каждой: какой-нибудь из вариантов восстановления исходных последовательностей, которые при слиянии дадут тот же результат. Если
в исходных данных в последовательности стояло число, то в выходных данных на том же месте должно стоять то же число.
|
Ввод |
Вывод |
2
? 4
3 ?
1 3 4 5 |
1 4
3 5 |