CF906E.Reverses

Hurricane came to Berland and to suburbs Stringsvill. You are going to it to check if it's all right with you favorite string. Hurrinace broke it a bit by reversing some of its non-intersecting substrings. You have a photo of this string before hurricane and you want to restore it to original state using reversing minimum possible number of its substrings and find out which substrings you should reverse.

You are given a string s — original state of your string and string t — state of the string after hurricane. You should select k non-intersecting substrings of t in such a way that after reverse of these substrings string will be equal s and k is minimum possible.

飓风袭击了贝尔兰以及其郊区——字符串镇（Stringsvill）。你正前往那里，检查你最喜爱的字符串是否安然无恙。飓风对它造成了一定破坏：通过翻转该字符串中若干个互不相交的子串，改变了它的形态。你手中有一张该字符串在飓风前的照片，现在希望仅通过翻转尽可能少的子串，将当前字符串恢复为原始状态，并确定需要翻转哪些子串。

给定字符串 $s$ —— 字符串的原始状态，以及字符串 $t$ —— 飓风后的状态。你需要从 $t$ 中选出 $k$ 个互不相交的子串，使得将这些子串各自翻转后，$t$ 恰好变为 $s$，且 $k$ 为可能的最小值。

First line of input contains string s and second line contains string t. Both strings have same length and consist of lowercase English letters. 1 ≤ |s| = |t| ≤ 5·105

输入的第一行包含字符串 $s$，第二行包含字符串 $t$。两个字符串长度相同，且均由小写英文字母组成。$1 \le |s| = |t| \le 5\cdot10^5$

In first line print k — minimum number of substrings you should reverse. Next output k lines. Each line should contain two integers l__i, r__i meaning that you should reverse substring from symbol number l__i to symbol r__i (strings are 1-indexed). These substrings shouldn't intersect. If there are multiple answers print any. If it's impossible to restore string output -1.

第一行输出 k —— 你需要翻转的子串的最少数量。接下来输出 k 行，每行包含两个整数 l__i、r__i，表示你需要翻转从第 l__i 个字符到第 r__i 个字符的子串（字符串下标从 1 开始）。这些子串之间不能相交。若存在多个答案，输出任意一个即可。若无法恢复该字符串，则输出 -1。