← 返回题目列表

Codeforces · 825/D

D. 合适的更换

中文机器翻译题面 查看原题

给定两个由小拉丁字母组成的字符串 s 和 t,字符串 s 也可以包含 '?'人物。

字符串 s 的适用性通过以下指标计算:

任意两个字母可以交换位置,这些操作可以在任意一对位置上执行任意次数。在所有结果字符串 s 中,选择字符串 t 出现次数最多的非相交字符串。适宜性是指出现的次数。

您应该替换所有“?”具有小拉丁字母的字符,使得字符串 s 的适用性最大。

输入

第一行包含字符串 s (1 ≤ |s| ≤ 106)。

第二行包含字符串 t (1 ≤ |t| ≤ 106)。

输出

用 '?' 打印字符串 s用小拉丁字母替换,以使该字符串的适用性最大。

如果存在多个具有最大适用性的字符串,则打印其中的任何一个。

示例

输入 #1

?aa?
ab

输出 #1

baab

输入 #2

??b?
za

输出 #2

azbz

输入 #3

abcd
abacaba

输出 #3

abcd

注意

在第一个示例中,字符串“baab”可以通过交换转换为“abab”,该字符串的适用性为 2。这意味着字符串“baab”的适用性也为 2。

在第二个示例中,您可以实现的最大适合度是 1,并且有几十个这样的字符串,“azbz”只是其中之一。

在第三个示例中没有“?”字符,字符串的适合度为 0。