ДНК роботів
Останні досягнення у технології синтезу ДНК дозволили провести експеримент по створенню біороботів.
Для полегшення завдання створення ПЗ для керування роботами було прийнято рішення, що їх ДНК буде складатись з M = 2^n символів для деякого n ≥ 2. Кріме цього, по технічним причинам це буде не звичайний рядок, а циклічний, тобто його можна починати читати з довільної позиції.
Одним із завдань експерименту є вивчення мутацій біороботів. В результаті тривалих спостережень було знайдено багато різних видів роботів. Для розуміння процесу мутації вченим необхідно розв'язати наступну задачу. Для ДНК двох роботів потрібно визначити коефіцієнт їх схожості. Він обчислюється, як максимальна кількість співпадаючих символів при найкращому суміщенні цих ДНК. Чим більше символів співпадає, тим краще суміщення.
Потрібно написати програму, яка знайде найкраще суміщення двох ДНК.
Вхідні дані
У першому рядку вхідного файлу записано одне число M (4 ≤ M ≤ 131072). У наступних двох рядках записані ДНК двох роботів. Обидві ДНК — рядки, які складаються рівно з M символів з множини {'A', 'C', 'G', 'T'}.
У вихідний файл виведіть два числа — максимальну кількість співпадаючих символів і значення оптимального здвигу — невід'ємна кількість символів другої ДНК, яку необхідно перенести з кінця рядка у його початок для досягнення найкращого суміщення.