We say that a word $s$ is almost equal to a word $r$ if the word $s$ can be transformed into the word $r$ using at most $k$ operations of one of the following types:

• inserting a letter at the beginning, at the end, or between two existing letters of the word $s$,
• deleting one of the letters of the word $s$,
• replacing a letter of the word $s$ with another.

You are given two words $t$ and $p$. Determine whether the word $t$ contains a substring* almost equal to the word $p$.

Input

The first line of the input contains a single integer $k$ ($0 \le k \le 10$), used to define the almost-equality relation of words. The second and third lines of the input contain the words $t$ and $p$, respectively. Each of these words consists of at least one and at most $100\,000$ lowercase English letters.

Output

If the word $t$ does not contain a substring almost equal to the word $p$, output the word NIE in a single line.

Otherwise, output two integers $a, b$ ($1 \le a \le b \le |t|$) in a single line, such that the substring of $t$ starting at position $a$ and ending at position $b$ is almost equal to the word $p$.

Positions in the word are consecutive natural numbers. The leftmost letter is at position 1.

If there are multiple solutions, any of them will be accepted as correct.

Examples

Input 1

1
abcd
abd

Output 1

1 2

Input 2

1
abcd
bde

Output 2

NIE

*For a given word $t = c_1c_2 \dots c_n$, a substring of $t$ is any word of the form $c_a \dots c_b$, where $1 \le a \le b \le n$.