403788: GYM101306 A Palindrome Password
Description
Your first mission is to find the password of the Martian database. To achieve this, your best secret agents have already discovered the following facts:
- The password is a substring of a given string composed of a sequence of non-decreasing digits
- The password is as long as possible
- The password is always a palindrome
A palindrome is a string that reads the same backwards. racecar, bob, and noon are famous examples.
Given those facts, can you find all possible passwords of the database?
InputThe first line contains n, the length of the input string (1 ≤ n ≤ 105).
The next line contains a string of length n. Every character of this string is a digit.
The digits in the string are in non-decreasing order.
OutputOn the first line, print the number of possible passwords, k.
On the next k lines, print the possible passwords in alphabetical order.
ExamplesInput8Output
34456788
2Input
44
88
1Output
0
1Note
0
You can easily convert a digit encoded as a character to an integer:
(int)('1' - '0') will give you 1 for instance, in C++ or Java.
int('4' - '0') will give you 4 in Python.