102845: [AtCoder]ABC284 F - ABCBAC

Problem Statement

For a string $S$ of length $N$ and an integer $i\ (0\leq i\leq N)$, let us define the string $f_i(S)$ as the concatenation of:

• the first $i$ characters of $S$,
• the reversal of $S$, and
• the last $(N-i)$ characters of $S$,

in this order. For instance, if $S=$ abc and $i=2$, we have $f_i(S)=$ abcbac.

You are given a string $T$ of length $2N$. Find a pair of a string $S$ of length $N$ and an integer $i\ (0\leq i\leq N)$ such that $f_i(S)=T$. If no such pair of $S$ and $i$ exists, report that fact.

Constraints

• $1\leq N \leq 10^6$
• $N$ is an integer.
• $T$ is a string of length $2N$ consisting of lowercase English letters.

Input

The input is given from Standard Input in the following format:

$N$ 
$T$

Output

If no pair of $S$ and $i$ satisfies the condition, print -1. Otherwise, print $S$ and $i$, separated by a newline. If multiple pairs of $S$ and $i$ satisfy the condition, you may print any of them.

Sample Input 1

3
abcbac

Sample Output 1

abc
2

As mentioned in the problem statement, if $S=$ abc and $i=2$, we have $f_i(S)=$ abcbac, which equals $T$, so you should print abc and $2$.

Sample Input 2

4
abababab

Sample Output 2

abab
1

$S=$ abab and $i=3$ also satisfy the condition.

Sample Input 3

3
agccga

Sample Output 3

cga
0

$S=$ agc and $i=3$ also satisfy the condition.

Sample Input 4

4
atcodeer

Sample Output 4

-1

If no pair of $S$ and $i$ satisfies the condition, print -1.

问题描述

对于长度为$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$。找出一个长度为$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$。如果有多个满足条件的$S$和$i$，你可以打印其中任意一对。

样例输入1

3
abcbac

样例输出1

abc
2

如问题描述中提到的，如果$S=$ abc 和 $i=2$，我们有$f_i(S)=$ abcbac，等于$T$，所以你应该打印abc和$2$。

样例输入2

4
abababab

样例输出2

abab
1

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

样例输入3

3
agccga

样例输出3

cga
0

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

样例输入4

4
atcodeer

样例输出4

-1

如果不存在满足条件的$S$和$i$，打印-1。