Migrated from Lutece 2657 模仿者

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

第五章：模仿者

选拔结束了，陈家洛顺利通过选拔进入了石马国代表队。 一些尘封已久的秘密也开始拉开帷幕。。。。。。

要参加区域码力大会，自然会需要结界钥匙，因为相传区域码力大会是办在破碎的漂浮空间结界之中的，从上古尘封至今的漂浮空间隐藏了凡人所不能想象的大机缘。为了让代码大陆上的年轻人能公平竞争，码力委员会每年都会举办区域码力大会，让各国的顶尖年轻人自己进入上古空间争夺机缘。至于结界钥匙的发放则一直是个迷。传说，石马国每年都会举办祭祀，以从上古空间中召唤钥匙。今年，陈家洛终于有机会一探究竟了。可是，他终究没想到，事情竟会令他痛苦欲绝。 在去参加祭祀前，香香公主突然将他叫道了她的房间。这还是陈家洛第一次进女孩子的闺房。出乎意料的是，她的房间非常朴素，连衣柜都没有。“她不换衣服吗？”陈家洛有点疑惑。 “土豆，我很高兴能看到你能成功通过选拔。但是那天你朋友圈发的你只爱acm是什么意思，你不爱我了吗？”香香公主嗔怒道。 “啊这，那怎么可能？”陈家洛脑子飞快旋转，只想快点想到个解释的理由。但是不得不承认，正如同当年他放弃香香公主试图换取反清复明一样，事业心强的人总喜欢把一些事情放在儿女情长之上。 “别解释了，解释就是掩饰，掩饰的就是事实，果然爱会消失是吧，我们分手吧！”，话音刚落，她便闪身出去，再也没有回头。 陈家洛看向她远去的身影，却抬不动脚步去追，因为结界钥匙马上就要发放了，他猛地扇了自己一巴掌，“陈家洛啊陈家洛，大禹三过家门而不入，你这样怎能成得了大事。”然后便向祭坛跑去。 “如果我不狠心，你又怎能做你真正想做的事情，你又怎能，，，，忘了，我？”他走后，房间的不知道哪个角落传来了幽幽的叹息。

祭祀开始了，只见 Vingying 熟练的操作祭坛，显然不是第一次祭祀了。祭坛中，忽然凝聚起了白色的码力，，烟雾升起，码力之中似乎有什么东西被召唤而来。 白色的雾气持续了半炷香时间便慢慢消散，忽然人群中传来了一声悲痛欲绝的叫声，竟是从陈家洛口中传来。 他目眦尽裂地看向祭坛，烟雾消散的那一刻，他仿佛看到了香香公主的身影，慢慢化为白色的晶体，然后碎成一片片钥匙。 朴素的房间，银川星海湖畔的苗人凤，Namazabi12 的算命，香香公主的神秘身世，一切的一切慢慢在陈家洛脑海中串联，成型。原来往年，钥匙都会直接召唤到祭坛，但是今天仿佛有什么不同，钥匙以香香公主的形态出现在了长白山脉，来到了土豆身边。 “原来你本来就不是人，原来你就是上古密阵的钥匙！”陈家洛哭喊道。怪不得她会以那样奇怪的理由离开，她是怕我忘不了她吧。可惜我还是看到了，还好我看到了！你还留有钥匙，照玄幻小说的说法，只要你留有什么就一定能复活的对吧，我一定能复活你的！ 但他不能放歌，悄悄不但是别离的笙箫，更是祭祀的要求，所以他要用红花会的模仿者在这里祭祀，自己去外面哭。

土豆使用了模仿者。 模仿者最初和土豆并不一定相同，他可以变换自己的基因序列以模仿土豆的基因。 土豆的基因是一串小写英文字母，模仿者也是。 模仿者可以挑选一些不相交的连续基因段，并将这些基因段翻转，从而和土豆的基因相同。 请帮助模仿者选择最少的段翻转，来模仿土豆。

Input

输入包括两行，第一行土豆的基因 $s$，第二行模仿者的初始基因 $t$。保证两者长度相等。

Output

第一行输出一个整数 $k$ 表示需要翻转的基因段段数。

随后跟着 $k$ 行，每行包括两个整数 $a_i, b_i$，表示翻转模仿者的从第 $a_i$ 个到第 $b_i$ 个的基因段（字符串下标从 $1$ 开始）。请保证 $a_i$ 的递增。

如果有多组答案，请输出使 $a_i$ 字典序最小的一组答案，字典序最小是指，对于两不同的数组 $c, d$，如果前 $i$ 个数相同而第 $i+1$ 个不同，若 $c_{i+1}<d_{i+1}$，则 $c$ 的字典序较小。

如果模仿者无法模仿土豆，请输出 $-1$。

Samples

abcxxxdef
cbaxxxfed

2
1 3
7 9

Constraints

$1 \le |s|=|t| \le 5\times 10^5$

Resources

2021 UESTC ICPC Training for String and Search Algorithm