题目描述

给定一个长度为 $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_i(S) = \text{abcbac}$。

现在，给定一个长度为 $2N$ 的字符串 $T$。找出一个长度为 $N$ 的字符串 $S$ 和一个整数 $i$ $(0 \leq i \leq N)$，使得 $f_i(S) = T$。如果不存在这样的 $S$ 和 $i$，则输出报告该事实。

约束条件

• $1 \leq N \leq 10^6$
• $N$ 是一个整数。
• $T$ 是一个由小写英文字母组成的长度为 $2N$ 的字符串。

输入

输入从标准输入中给出，格式如下：

N

T

输出

如果没有满足条件的 $S$ 和 $i$ 的组合，输出 $-1$。否则，输出字符串 $S$ 和整数 $i$，以换行分隔。如果存在多个符合条件的组合，你可以输出任意一个。

示例输入 1

3
abcbac

示例输出 1

abc
2

如题目所述，如果 $S = \text{abc}$ 且 $i = 2$，我们得到 $f_i(S) = \text{abcbac}$，这等于 $T$，因此应输出 abc 和 2。

示例输入 2

4
abababab

示例输出 2

abab
1

$S = \text{abab}$ 和 $i = 3$ 也满足条件。

示例输入 3

3
agccga

示例输出 3

cga
0

$S = \text{agc}$ 和 $i = 3$ 也满足条件。

示例输入 4

4
atcodeer

示例输出 4

-1

如果没有满足条件的 $S$ 和 $i$ 的组合，输出 $-1$。