Description

艾莉博士与外星文明建立了联系。他们偶然发现了一群口吃的外星人！最重要的单词有可能重叠重复出现多次。在消息$babab$中，$bab$重叠重复出现两次。给定一个整数$m$ 和消息字符串$s$，找到$s$中至少出现$m$次的最长子串。在消息$baaaababababbababbab$中，长度为$5$的子串$babab$出现了$3$次，起始位置分别为$5$、$7$和$12$（下标从$0$开始），没有更长的子串出现$3$次以上（参见输入样例$1$）。

Format

Input

输入包含几个测试用例。每个测试用例的第$1$行都包含一个整数$m （m ≥1）$，表示最小重复次数，后跟一行字符串$s$（长度为$m～40000$，含$40000$）。$s$ 中的所有字符都是$a ～z$ 的小写字符。最后一个测试用例用$m =0$表示，不处理。

Output

对每个测试用例，都输出一行，若没有解决方案，则输出$none$；否则单行输出两个整数，以空格分隔。第$1$个整数表示至少出现$m$次的最长子串长度；第2个整数表示最右边子串的起始位置。

Samples

3
baaaababababbababbab
11
baaaababababbababbab
3
cccccc
0

5 12
none
4 2