You are given two strings $s$ and $t$. The string $s$ may contain some question marks, representing undetermined characters, while the remaining positions in $s$ and all characters in $t$ are lowercase English letters.

You need to replace each question mark in $s$ with a lowercase English letter such that the number of occurrences of $t$ in $s$ is maximized. If there are multiple optimal solutions, you may output any one of them.

Input

The input consists of two lines, containing strings $s$ and $t$ respectively.

Output

Output two lines. The first line should contain the maximum possible number of occurrences of $t$ in $s$. The second line should contain any one version of $s$ after filling in the question marks that achieves this maximum.

Examples

Input 1

wq?qwqs???c?c?????
qwq

Output 1

5
wqwqwqsqwqcucqwqwq

Constraints

For all data, $|s|, |t| \le 10^5$.

Subtask 1 (20 pts): $s$ contains no question marks.

Subtask 2 (10 pts): $|s|, |t| \le 50$.

Subtask 3 (30 pts): $|s|, |t| \le 1000$.

Subtask 4 (40 pts): No additional constraints.