Задача J. Искренняя предусмотрительность

Задачу добавил: alef

Успешно сдано решений: 7

Ограничения: время на тест - 2с, память - 256 Мб

Техники Очень Большой Корпорации оказались на высоте, и собрали ноутбук из привезенных Василием деталей быстрее, чем Земля совершила полный оборот вокруг своей оси. Очень Мудрый Руководитель был столь доволен, что немедленно поручил Василию установить на этот ноутбук древнюю операционную систему Moonix, о которой услышал от своей дочки за ужином.

Василий, предполагавший, что его миссия уже завершена, был озадачен. Оказалось, что древние операционные системы устанавливались в ноутбук не аппаратно, в виде специальной платы, как он предполагал, а программно. Описание процесса установки и вовсе заставили его загрустить. Но тут он вспомнил, что на прощание весельчак Диего, которому он рассказал и про Очень Мудрого Руководителя, и про его дочку, подарил ему небольшой кристалл памяти со словами: "Тогда тебе пригодится эта часть моей коллекции".

Компьютер Василия сообщил, что информация на кристалле зашифрована, за исключением одного фрагмента с названием "ПрочтиМеня!". Василий открыл фрагмент и увидел текст, описывающий содержимое кристалла. Да, там действительно было все, что нужно. Мысленно еще раз поблагодарив Диего, Василий дочитал файл до конца.
"Чтобы получить доступ к остальной части информации, Вам необходимо ввести код, состоящий из десятичных цифр. В каждой из следующих N строк записано по одному целому положительному числу, некоторые цифры в котором заменены вопросительными знаками. В (N+1)-ой строке содержится их сумма. Найдите, какие цифры скрыты за вопросительными знаками, выпишите их подряд - и это будет код".
Ваша задача - отыскать эти цифры.

Формат входного файла input.txt
Первая строка - целое число N (2 <= N <= 10^5) - количество целых положительных чисел
В каждой из следующих N строк содержится по одному натуральному числу, строго меньшему 10^13, некоторые цифры которого заменены вопросительными знаками (одному знаку всегда соответствует одна цифра)
В последней строке содержится сумма этих N чисел - натуральное число, строго меньшее 10^18.
Все числа записаны без ведущих нулей.

Формат выходного файла output.txt
Выходной файл содержит N строк, в каждой из которых записано соответствующее (входному файлу) число с восстановленными цифрами. Все числа должны быть записаны без ведущих нулей.
Если решения не существует, в первой (и единственной) строке файла выведите "No solution" (без кавычек)
Если существует несколько решений - выведите любое из них.

Пример входного файла - 1
2
?
1?
11

Пример выходного файла - 1
1
10
(пояснение: 1 + 10 = 11)

Пример входного файла - 2
2
?
1?
12

Пример выходного файла - 2
2
10
(пояснение: 2 + 10 = 12; также допустим ответ 11: 1 + 11 = 12)

Пример входного файла - 3
2
?
1?
29

Пример выходного файла - 3
No solution

Пример входного файла - 4
2
12
?9
21

Пример выходного файла -4
No solution


Сдать задачу

Задать вопрос жюри по этой задаче