← 返回题目列表

Codeforces · 527/B

B. 错误纠正系统

中文机器翻译题面 查看原题

Ford Prefect 在一家生产毛巾的小公司找到了一份网络开发人员的工作。他目前的工作任务是为公司网站创建一个搜索引擎。在开发过程中,他需要编写一个子程序来比较长度相等的字符串S和T是否“相似”。在网上简单搜索后,他了解到两个相同长度的字符串S和T之间的汉明距离,其定义为S和T具有不同字符的位置数。例如,单词“permanent”和“pergament”之间的汉明距离是二,因为这些单词的第四个和第六个字母不同。

而且,在搜索信息的过程中,他还注意到现代搜索引擎拥有强大的机制来纠正请求中的错误,以提高搜索质量。福特对人类了解不多,因此他认为请求中最常见的错误是交换字符串中的两个任意字母(不一定是相邻的)。现在他想编写一个函数,确定应该交换字符串S中的哪两个字母,使得新字符串S和字符串T之间的汉明距离尽可能小,否则,确定这样的替换不能减少字符串之间的距离。

帮助他做到这一点!

输入

第一行包含整数 n (1 ≤ n ≤ 200 000) — 字符串 S 和 T 的长度。

第二行包含字符串 S。

第三行包含字符串 T。

每行仅包含小写拉丁字母。

输出

在第一行中,打印数字 x — 如果交换 S 中最多一对字母,则字符串 S 和 T 之间可能的最小汉明距离。

在第二行中,如果可以通过交换位置 i 和 j 上的字母来达到最小可能距离,则打印索引 i 和 j (1 ≤ i, j ≤ n, i ≠ j),或者如果不需要交换字符,则打印“-1 -1”。

如果有多个可能的答案,请打印其中任何一个。

示例

输入 #1

9
pergament
permanent

输出 #1

1
4 6

输入 #2

6
wookie
cookie

输出 #2

1
-1 -1

输入 #3

4
petr
egor

输出 #3

2
1 2

输入#4

6
double
bundle

输出#4

2
4 1

注意

在第二个测试中,打印 i = 2, j = 3 是可以接受的。