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 是可以接受的。