Martians` DNA Analysis
After recent disciveries of remains of ancient Martian civilization, many biology specialists lay their hopes to DNA analysis of Martians. The task is complicated by the fact that unlike human DNA that only contains four nucleotides, Martians must have had more advanced organisms, so their DNA contains upto 36 nucleotides.
One step of analysis is detecting blocks that are repsonsible for some particular organism properties. But how can one identify complete blocks? One way to do so, is to search for so called maximal repetitions. Let us consider DNA as a stringω, where each character identifies some nucleotide. A non-empty substring of the string is called a maximal repetition if it is both left-branching and right-branching. The string α is called left-branching there are two different characters c_1 andc_2, such that both c_1α and c_2α are substrings of $ω (here '$' is a character that does not occur in ω, it is introduced so that string that is prefix of ω and occurs somwhere else in it were left-branching). Similarly, α is right branching if both αc_1 and αc_2 are substrings of ω$ for some different c_1 and c_2. Long maximal repetitions are good candidates for complete blocks.
Given a string that represents a Martian’s DNA, find the number of different (as strings) maximal repetitions in it, the length of the longest maximal repetition in it, and the number of its longest maximal repetitions.
Input
Input file contains non-empty string that contains only capital latin letters and digits and represents a Martian’s DNA. The length of the string does not exceed 6000.
Output
Output the number of maximal repetitions in the DNA, the length of its longest maximal repetition, and the number of maximal repetitions that have this length. If there are no maximal repetitions, output three zeroes.