F - ABCBAC Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 が与えられます。 f_i(S)=T を満たす長さ N の文字列 S と整数 i\ (0\leq i\leq N) の組を 1 つ見つけてください。 そのような 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 を出力してください。

Score : 500 points

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.