Задача поиска заданной подстроки в тексте имеет неоспоримое значение и ее решение реализовано в большинстве языков программирования в виде функциональности стандартной библиотеки. Однако, зачастую необходимо решать задачу неточного поиска. Назовем расстоянием между двумя строками a и b наименьшее количество операций, необходимое для того, чтобы строку a перевести в строку b. Разрешенные операции: замена любого символа любым другим, вставка любого символа в произвольную позицию в строке и удаление произвольного символа. Например, расстояние между строками "кот" и "конь" равно 2. Ваша задача в заданном тексте найти подстроку, которая имеет расстояние до заданной не более d.
В первой строке записана строка в которой следует осуществлять поиск. Длина строки не менее 1 символа и не более 2·10^6. Далее содержится строка, содержащая образец поиска. Его длина не менее 1 символа и не более 50 символов. Заданные строки содержат строчные и прописные буквы латинского алфавита и цифры. Последняя строка содержит целое число d (0 ≤ d ≤ 50) – наибольшее расстояние между образцом поиска и искомой подстрокой.
Выведите два целых числа start, length, где start – позиция первого символа найденной подстроки, а length – ее длина. Нумерация символов в строке начинается с нуля. Если решений несколько, выведите любое.