补全暗号

小宁记录了一串只含 0、1、? 的暗号 $s$．每个 ? 都必须替换为 0 或 1，其他字符不能修改．另有一串非空的二进制模式 $t$．

补全以后，数一数有多少个位置使得从该位置开始的连续 $|t|$ 个字符恰好等于 $t$．不同出现可以重叠．

请先使出现次数最大；若有多种补全方案达到最大次数，输出其中字典序最小的一个．在字典序中，0 小于 1．

输入格式

第一行输入字符串 $s$．第二行输入字符串 $t$．

输出格式

第一行输出最大的出现次数．第二行输出对应的字典序最小的补全串．

样例 1

?0??
01

1
0001

暗号 0001 的第 $3$ 至第 $4$ 位出现一次 01．无法出现两次；达到一次的补全串中，它的字典序最小．

样例 2

????
01

2
0101

更多样例

点击下载本题选手目录

以下样例均为独立构造，供本地自测；通过样例不代表可以获得对应子任务的分数．

数据范围与子任务

$1\le|t|\le|s|\le2\times10^5$，$|s| \times |t|\le4\times10^6$．$s$ 只含 0、1、?，$t$ 只含 0、1．各子任务独立计分；只有通过一个子任务的全部测试点，才能获得该子任务的分数．