Substring Reversal

Interview

Time limit1sMemory limit1024 MB

Summary

Given an original string and the result of reversing one substring of length at least two, find the reversed segment, preferring the smallest start then end.

Level: Medium4 of 10
Topics: String, Two pointers
Solved: No attempts yet

Problem

Glen enjoys studying various text transformations. Lately he is interested in so-called reversals. A reversal is a transformation in which one contiguous part of the text, made up of two or more characters, is written backwards while the rest of the text is left unchanged. For simplicity, Glen only considers texts made of uppercase Latin letters.

As an example, here are several reversal transformations of the text LABASRYTAS (the reversed parts are shown in bold).

LABASRYTAS → LASABRYTAS
LABASRYTAS → SATYRSABAL
LABASRYTAS → ALBASRYTAS

Glen has just received two different texts and is convinced that the second text was obtained from the first by performing exactly one reversal operation. However, Glen cannot tell exactly which part was reversed.

Could you help Glen find the reversed part?

Input

The first line contains the length $N$ of the original (and transformed) text. The second line contains the original text, and the third line contains the transformed text.

Both texts consist solely of uppercase Latin letters.

The input is always such that a solution exists, and the original text differs from the text after the reversal.

Output

Output two integers: the numbers of the first and last characters of the reversed part of the text. Characters are numbered from left to right, from $1$ to $N$ .

If several answers are possible, output the one whose first character has the smallest number. If several answers still remain, output the one whose last character has the smallest number.

Constraints

$2 \le N \le 100000$

Examples2

Example 1
Input
```
7
SAVASIS
SAVSAIS
```
Expected output
```
4 5
```
Example 2
Input
```
10
LABASRYTAS
LASABRYTAS
```
Expected output
```
3 5
```