{"raw_statement":[{"iden":"statement","content":"You are given two strings _s_ and _t_ consisting of small Latin letters, string _s_ can also contain _'?'_ characters.\n\n_Suitability_ of string _s_ is calculated by following metric:\n\nAny two letters can be swapped positions, these operations can be performed arbitrary number of times over any pair of positions. Among all resulting strings _s_, you choose the one with the largest number of **non-intersecting** occurrences of string _t_. _Suitability_ is this number of occurrences.\n\nYou should replace all _'?'_ characters with small Latin letters in such a way that the _suitability_ of string _s_ is maximal."},{"iden":"input","content":"The first line contains string _s_ (1 ≤ |_s_| ≤ 106).\n\nThe second line contains string _t_ (1 ≤ |_t_| ≤ 106)."},{"iden":"output","content":"Print string _s_ with _'?'_ replaced with small Latin letters in such a way that _suitability_ of that string is maximal.\n\nIf there are multiple strings with maximal _suitability_ then print any of them."},{"iden":"examples","content":"Input\n\n?aa?\nab\n\nOutput\n\nbaab\n\nInput\n\n??b?\nza\n\nOutput\n\nazbz\n\nInput\n\nabcd\nabacaba\n\nOutput\n\nabcd"},{"iden":"note","content":"In the first example string _\"baab\"_ can be transformed to _\"abab\"_ with swaps, this one has _suitability_ of _2_. That means that string _\"baab\"_ also has _suitability_ of _2_.\n\nIn the second example maximal _suitability_ you can achieve is _1_ and there are several dozens of such strings, _\"azbz\"_ is just one of them.\n\nIn the third example there are no _'?'_ characters and the _suitability_ of the string is _0_."}],"translated_statement":[{"iden":"statement","content":"你被给定两个由小写拉丁字母组成的字符串 #cf_span[s] 和 #cf_span[t]，字符串 #cf_span[s] 中也可能包含 _'?'_ 字符。\n\n字符串 #cf_span[s] 的 _适宜性_ 按如下方式计算：\n\n可以任意交换任意两个字符的位置，这种操作可以对任意位置对执行任意多次。在所有可能得到的字符串 #cf_span[s] 中，你选择具有最多 *不相交* 的子串 #cf_span[t] 出现次数的那个。_适宜性_ 即为这个出现次数。\n\n你需要将所有 _'?'_ 字符替换为小写拉丁字母，使得字符串 #cf_span[s] 的 _适宜性_ 最大化。\n\n第一行包含字符串 #cf_span[s]（#cf_span[1 ≤ |s| ≤ 106]）。\n\n第二行包含字符串 #cf_span[t]（#cf_span[1 ≤ |t| ≤ 106]）。\n\n请输出将 #cf_span[s] 中的 _'?'_ 替换为小写拉丁字母后的字符串，使得其 _适宜性_ 最大。\n\n如果有多个字符串具有最大 _适宜性_，输出其中任意一个即可。\n\n在第一个例子中，字符串 _\"baab\"_ 可以通过交换变换为 _\"abab\"_，后者具有 _适宜性_ 为 _2_。这意味着字符串 _\"baab\"_ 的 _适宜性_ 也为 _2_。\n\n在第二个例子中，你能达到的最大 _适宜性_ 为 _1_，有数十种这样的字符串，_\"azbz\"_ 只是其中之一。\n\n在第三个例子中，字符串中没有 _'?'_ 字符，其 _适宜性_ 为 _0_。\n\n"},{"iden":"input","content":"第一行包含字符串 #cf_span[s]（#cf_span[1 ≤ |s| ≤ 106]）。第二行包含字符串 #cf_span[t]（#cf_span[1 ≤ |t| ≤ 106]）。"},{"iden":"output","content":"请输出将 #cf_span[s] 中的 _'?'_ 替换为小写拉丁字母后的字符串，使得其 _适宜性_ 最大。如果有多个字符串具有最大 _适宜性_，输出其中任意一个即可。"},{"iden":"examples","content":"输入\n?aa?ab\n输出\nbaab\n\n输入\n??b?za\n输出\nazbz\n\n输入\nabcd\n输出\nabcdabacaba"},{"iden":"note","content":"在第一个例子中，字符串 _\"baab\"_ 可以通过交换变换为 _\"abab\"_，后者具有 _适宜性_ 为 _2_。这意味着字符串 _\"baab\"_ 的 _适宜性_ 也为 _2_。在第二个例子中，你能达到的最大 _适宜性_ 为 _1_，有数十种这样的字符串，_\"azbz\"_ 只是其中之一。在第三个例子中，字符串中没有 _'?'_ 字符，其 _适宜性_ 为 _0_。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s \\in (\\Sigma \\cup \\{?\\})^* $ be the input string, where $ \\Sigma $ is the set of lowercase Latin letters.  \nLet $ t \\in \\Sigma^* $ be the target string.  \nLet $ n = |s| $, $ m = |t| $.  \n\nA *swap* is any transposition of two characters in $ s $.  \nA *non-intersecting occurrence* of $ t $ in $ s $ is a substring $ s[i:i+m-1] $ such that it equals $ t $ as a multiset (i.e., after arbitrary swaps, the multiset of characters matches that of $ t $), and no two such occurrences share a position.  \n\nThe *suitability* of $ s $ is the maximum number of non-overlapping (i.e., disjoint in indices) multisets of size $ m $ in $ s $, each having the same character frequencies as $ t $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^6 $  \n2. $ 1 \\leq m \\leq 10^6 $  \n3. $ m \\leq n $  \n4. Each character in $ t $ is in $ \\Sigma $.  \n5. Each character in $ s $ is either in $ \\Sigma $ or is $ ? $.  \n\n**Objective**  \nReplace each $ ? $ in $ s $ with a character from $ \\Sigma $ to maximize the number of non-intersecting occurrences of $ t $ (as multisets).  \nOutput any resulting string $ s' $ achieving this maximum suitability.","simple_statement":null,"has_page_source":false}