Reverses

题意翻译

给你两个长度为 $n$ 的字符串 $s$ 和 $t$。你可以翻转 $t$ 的若干个不相交的区间，要求最终 $s$ 和 $t$ 相同。问你最少翻转几个区间，并输出方案。

题目描述

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.

输入输出格式

输入格式

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·10^{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.

输入输出样例

输入样例 #1

abcxxxdef
cbaxxxfed

输出样例 #1

2
7 9
1 3