Даны две строки s и t, состоящие из строчных латинских букв, в строке s могут также встречаться символы '?'.
Пригодность строки s подсчитывается следующим способом:
Две любые буквы можно поменять местами, такую операцию можно проделывать неограниченное число раз над любой парой позиций. Среди всех полученных строк s выберите такую, что количество непересекающихся вхождений строки t в нее максимально. Пригодность — это полученное максимальное количество.
Замените все символы '?' строчными латинскими буквами таким образом, чтобы пригодность строки s была максимальна.
Выходные данные
Выведите строку s с символами '?', замененными строчными латинскими буквами таким образом, чтобы пригодность этой строки была максимальна.
Если есть несколько строк с максимальной пригодностью, то выведите любую.
Примечание
В первом примере строка "baab" может быть преобразована в "abab", у которой пригодность равна 2. Значит и у строки "baab" такая же пригодность.
Во втором примере максимальная возможная пригодность равна 1, и таких строк несколько десятков, "azbz" — одна из них.
В третьем примере в строке нет символов '?', а ее пригодность равна 0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
?aa?
ab
|
baab
|
|
2
|
??b?
za
|
azbz
|
|
3
|
abcd
abacaba
|
abcd
|