4. Поиск с ошибкой
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Напишите программу для поиска подстроки в строке. Дополнительное условие: разрешена одна ошибка, то есть одна пара символов может не совпадать.

Входные данные

В первой строке входных данных записана строка $$$s$$$, в которой ищем. Во второй строке записана подстрока $$$q$$$, которую ищем. Строки содержат только строчные латинские буквы, а их длины не превышают $$$2 \cdot 10^5$$$ символов.

Выходные данные

Выведите одно целое число — позицию вхождения подстроки $$$q$$$ в строку $$$s$$$ (позиции нумеруются с единицы). Если есть несколько верных ответов, то выведите наименьший из них. Если нет ни одного вхождения, то выведите 0.

Пример
Входные данные
abacabadaba
bad
Выходные данные
2
Примечание

Решения, работающие для строк длиной до 1000 символов, могут получить до 40 баллов.