DNA Robot#1841
Recent advances in DNA synthesis technology have enabled experiments in creating biorobots.
To simplify the development of software for robot control, it was decided that their DNA would consist of M = 2^n characters for some n \geq 2. Moreover, for technical reasons, this will not be a regular string, but a cyclic one, meaning it can be read starting from any position.
One of the objectives of the experiment is to study mutations in biorobots. As a result of prolonged observation, many different types of robots have been discovered. To understand the mutation process, scientists need to solve the following problem. Given the DNA of two robots, it is required to determine their similarity coefficient. It is calculated as the maximum number of matching characters in the best possible alignment of these DNA sequences. The more characters match, the better the alignment.
You are required to write a program that finds the best alignment of two DNA sequences.
The first line of the input contains a single integer (4 \leq M \leq 131072). The next two lines contain the DNA of the two robots. Both are strings consisting of exactly characters, each from the set \{'A', 'C', 'G', 'T'\}.
Output two numbers: the maximum number of matching characters and the optimal shift value — the non-negative number of characters from the end of the second DNA that must be moved to the start to achieve the best alignment.
Example 1