У вашего одноклассника, которого вы не очень любите за его занудство, но уважаете за его ум, были обнаружены две строки: строка t длины m и строка s длины n. Последовательность индексов p1, p2, ..., pm, где 1<=p1<p2<…<pm<=n, называется хорошей , если spi=ti для всех i от 1 до m. Шириной последовательности называется величина \(\max_{i = 1}^{m - 1} \left(p_{i + 1} - p_i\right)\), то есть максимальная разность между соседними элементами последовательности p.
Помогите однокласснику найти хорошую последовательность индексов с максимальной шириной. Одноклассник обещал вам, что строки s и t таковы, что хотя бы одна хорошая последовательность точно существует.
Входные данные
Первая строка входных данных содержит два числа n и m (2<=m<=n<=200000) - длины строк s и t соответственно.
Во второй строке входных данных задана строка s, состоящая из строчных букв английского алфавита, а в третьей строке задана строка t, состоящая из строчных букв английского алфавита.
Гарантируется, что существует хотя бы одна хорошая последовательность индексов.
Выходные данные
Выведите одно число - максимальную ширину хорошей последовательности.
Примечание
В первом примере из условия существуют две хорошие последовательности с шириной 3: это {1,2,5} и {1,4,5}.
Во втором примере из условия хорошая последовательность максимальной ширины — это {1,5}.
В третьем примере из условия есть лишь одна хорошая последовательность — это {1,2,3,4,5}.
В четвёртом примере из условия есть лишь одна хорошая последовательность — это {1,2}.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5 3
abbbc
abc
|
3
|
| 2 |
5 2
aaaaa
aa
|
4
|
| 3 |
5 5
abcdf
abcdf
|
1
|
| 4 |
2 2
ab
ab
|
1
|