题目描述

对于长度为$N$的字符串$S$和整数$i$（$0 \leq i \leq N$），定义字符串$f_i(S)$为以下三部分的连接：

1. $S$的前$i$个字符，
2. $S$的反转，以及
3. $S$的最后$(N-i)$个字符。

当$S = \text{abc}$且$i = 2$时，$f_2(S) = \text{abcbac}$。

给定长度为$2N$的字符串$T$，找到满足$f_i(S) = T$的$(S, i)$对。若不存在这样的对，则返回$-1$。

输入格式

按照题目描述输入，$N$ 是字符串长度，$S$ 是对应的字符串。

• $N$
• $T$

输出格式

若无解，输出$-1$；否则输出$S$和$i$（用换行分隔）。若存在多组解，输出 $i$ 较小的一组解。

Note :后续可能会加 $SPJ$ ,使得输出任意的 $i$ 都是合法的。

样例

3
abcbac

abc
2

3
agccga

cga
0

4
kedakeda

-1

提示

在样例 $2$ 中，$i= 0$ 和 $i = 3$都是合法的，这里我们取最小的 $i = 0$ 。

数据范围

• $1 \leq N \leq 10^6$
• $T$仅包含小写英文字母。