当前没有测试数据。

F - ABCBAC

得分: $500$ 分

问题描述

对于一个长度为 $N$ 的字符串 $S$ 和一个整数 $i (0\leq i\leq N)$，我们定义字符串 $f_i(S)$ 为以下顺序连接的字符串:

• $S$ 的前 $i$ 个字符
• $S$ 的反转
• $S$ 的后 $N-i$ 个字符

例如，如果 $S=$ abc，$i=2$，那么 $f_i(S)=$ abcbac。

给定一个长度为 $2N$ 的字符串 $T$。 找到一个字符串 $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$，以换行符分隔。 如果存在多个满足条件的 $S$ 和 $i$，你可以输出任意一个。

3
abcbac

abc
2

如问题描述中所述，如果 $S=$ abc 而 $i=2$，那么 $f_i(S)=$ abcbac，是与 $T$ 相等的，所以你应该输出 abc 和 $2$。

4
abababab

abab
1

$S=$ abab 而 $i=3$ 也满足条件。

3
agccga

cga
0

$S=$ agc 而 $i=3$ 也满足条件。

4
atcodeer

-1

如果不存在满足条件的 $S$ 和 $i$，则输出 -1。