409280: GYM103476 A Missing Letters

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Missing Letterstime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

After the first snow this winter, students of Innopolis University built a string of letters out of snow. Unfortunately, over time, some of them have collapsed.

One student plans to rebuild new letters instead of the destroyed ones, but they want their initials (a two-letter string made up of the first letters of his first and last name) to appear as often as possible in the rebuilt string. Only occurrences where the student's initials appear as two consecutive letters count. Help them do it.

Input

The first line contains a string consisting of capital English letters and question marks. Question marks correspond to missing letters. The string length ranges from 1 to $$$10^5$$$ characters.

The second line contains a two-letter string — the student's initials.

Output

In the first line, print the maximum number of times the student's initials can appear in the string after replacing all question marks with letters. In the second line, print the string itself. If there are multiple answers, print any.

Scoring
SubtaskPointsConstraints
160Student's initials are two equal letters
240No additional constraints
ExamplesInput
I?NO?OLIS?PE?
OP
Output
2
INNOPOLISOPEN
Input
????
AA
Output
3
AAAA
Input
NONE
GG
Output
0
NONE

加入题单

上一题 下一题 算法标签: