[AdditionalFile5610.zip](file://AdditionalFile5610.zip?type=additional_file)

#5610. 「PA 2016 Final」Dopasowanie

标签: 传统 | 时间限制: 7000 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2016 Final Dopasowanie

如果通过对字符串 $s$ 进行不超过 $k$ 次以下类型的操作，可以将其转换为字符串 $r$，则称字符串 $s$ 与字符串 $r$ 是几乎相等的：

• 在字符串 $s$ 的开头、末尾或任意两个现有字母之间插入一个字母。
• 删除字符串 $s$ 中的一个字母。
• 将字符串 $s$ 中的某个字母替换为另一个字母。

给定两个字符串 $t$ 和 $p$。你需要判断字符串 $t$ 是否包含一个与字符串 $p$ 几乎相等的子串。

输入格式

第一行包含一个整数 $k$ $(0 \leq k \leq 10)$，用于定义字符串的几乎相等关系。

第二行和第三行分别包含字符串 $t$ 和 $p$。每个字符串由至少一个、至多 $100000$ 个小写英文字母组成。

输出格式

如果字符串 $t$ 中不包含与字符串 $p$ 几乎相等的子串，则在唯一的一行中输出单词 NIE。

否则，在唯一的一行中输出两个整数 $a, b$ $(1 \leq a \leq b \leq |t|)$，表示从位置 $a$ 开始到位置 $b$ 结束的字符串 $t$ 的子串与字符串 $p$ 几乎相等。

字符串中的位置由连续的自然数表示，最左边的字母位于位置 $1$。

如果存在多个解，输出其中任意一个均被视为正确。

样例 1

输入

1
abcd
abd

输出

1 2

样例 2

输入

1
abcd
bde

输出

NIE