Search for substrings with palindromic shift

PHP Hard strings

Task «Search for substrings with palindromic shift»

Given a string S consisting of lowercase Latin letters. It is necessary to find all unique substrings of length K that become palindromes after a cyclic shift to the left by one character. Output them in lexicographic order separated by commas. If there are no such substrings, output 'none'. Constraints: 1 ≤ |S| ≤ 10^5, 1 ≤ K ≤ |S|.

Input Format

Two strings: the first is an integer K, the second is a string S.

Output Format

A string with unique substrings separated by commas in lexicographic order or 'none'.

Examples

Example 1

INPUT

3
abacaba

OUTPUT

none

Example 2

INPUT

4
abcde

OUTPUT

none

Example 3

INPUT

2
aaabbb

OUTPUT

aa,bb

main.php