一个名叫 Ayrat 的男孩生活在 AMI-1511 星球上。这个星球上的每个居民都有天赋。具体来说,Ayrat热爱跑步,而且仅仅跑步对他来说还不够。他梦想让跑步成为一门真正的艺术。
首先,他想用涂层t建造跑道。在 AMI-1511 星球上,轨道的涂层是一系列彩色块,其中每个块都用小英文字母表示。因此,每一个涂层都可以被视为一根绳子。
不幸的是,方块不能自由出售给非商业客户,但 Ayrat 发现了无限数量的涂层。此外,他还有剪刀和胶水。 Ayrat 将购买一些涂层,然后从每个涂层中切出一个连续的部分(子串)并将其粘到轨道涂层的末端。此外,他可能会选择在粘合之前翻转该块。 Ayrat 想知道他需要购买的最少涂层数量才能为他的跑道获得涂层。当然,他也想知道一些方法来获得答案。
输入
输入的第一行包含字符串 s — 商店中存在的涂层。第二行包含字符串 t — Ayrat 想要获得的涂层。两个字符串都非空,仅由小英文字母组成,长度不超过2100。
输出
第一行应包含所需的最小涂层数 n 或 -1(如果无法创建所需的涂层)。
如果答案不是 -1,那么接下来的 n 行应该包含两个整数 xi 和 yi - 相应片段中结束块的数量。如果 xi ≤ yi 则按常规顺序使用该片段,如果 xi > yi 则按相反顺序使用该片段。按照粘合顺序打印这些碎片以获得字符串 t。
示例
输入 #1
abc cbaabc
输出 #1
2 3 1 1 3
输入 #2
aaabrytaaa ayrat
输出 #2
3 1 1 6 5 8 7
输入 #3
ami no
输出 #3
-1
注意
在第一个示例字符串“cbaabc”=“cba”+“abc”中。
在第二个示例中:“ayrat”=“a”+“yr”+“at”。