ABCBAC

题目描述

对于长度为 $N$ 的字符串 $S$ 和整数 $i\ (0 \le i \le N)$,定义字符串 $f_i(S)$ 为以下三部分按顺序拼接而成:

$S$ 的前 $i$ 个字符;

$S$ 的反转;

$S$ 的后 $(N-i)$ 个字符。

例如,若 $S=$ abc 且 $i=2$,则 $f_i(S)=$ abcbac。

给定一个长度为 $2N$ 的字符串 $T$。求一对长度为 $N$ 的字符串 $S$ 和整数 $i\ (0 \le i \le N)$,使得 $f_i(S)=T$。

若不存在这样的 $S$ 和 $i$,请报告这一事实。

输入格式

输入按以下格式从标准输入给出:

$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$。

数据范围

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

提示

答案不唯一,输出任意合法解即可。