全国知名的春季编程营新一期即将开营。于是,所有友好的策展人和老师团队开始制定夏令营的日程。经过不断的讨论,他们提出了一个时间表$$$s$$$,它可以表示为一个二进制字符串,其中如果学生将在第$$$i$$$日进行比赛,则第$$$i$$$个符号为“1”,如果他们休息一天,则为“0”。
在最后一刻,Gleb 说,如果按照时间表 $$$t$$$ 运行(可以用与时间表 $$$s$$$ 相同的格式描述),营地将是最有生产力的。由于当前的天数可能与时间表 $$$t$$$ 中的天数不同,Gleb 要求必须更改营地的时间表,以便 $$$t$$$ 作为子串在其中出现的次数尽可能多。同时,比赛日和休息日的数量不应改变,只是其顺序可以改变。
你能以最好的方式重新安排日程吗?
输入
第一行包含字符串 $$$s$$$ ($$$1 \leqslant |s| \leqslant 500\,000$$$),表示营地日程表的当前项目。
第二行包含字符串 $$$t$$$ ($$$1 \leqslant |t| \leqslant 500\,000$$$),表示根据 Gleb 的最佳调度。
字符串 $$$s$$$ 和 $$$t$$$ 仅包含字符“0”和“1”。
输出
在唯一一行中打印子字符串数量最多等于 $$$t$$$ 的时间表。打印的时间表应仅包含字符“0”和“1”,并且零的数量应等于 $$$s$$$ 中零的数量,而 1 的数量应等于 $$$s$$$ 中 1 的数量。
如果有多个最佳时间表,请打印其中任何一个。
示例
输入 #1
101101 110
输出 #1
110110
输入 #2
10010110 100011
输出 #2
01100011
输入 #3
10 11100
输出 #3
01
注意
在第一个示例中出现两次,一次从第一个位置开始,一次从第四个位置开始。
在第二个示例中,仅出现一次,从第三个位置开始。请注意,答案不是唯一的。例如,如果我们将第一天(休息日)移至最后一个位置,$$$t$$$ 出现的次数不会改变。
在第三个示例中,甚至不可能出现一次。