Your classmate, whom you don't really like for his tediousness, but respect for his intelligence, was found to have two strings: a string t length m ;and a string s length n. Index sequence p1, p2, ..., p< font size="1">m where 1<=p1<p2<…<pm<=n, is good if spi=ti for all i from 1 to m. The width of a sequence is the value of \(\max_{i = 1}^{m - 1 } \left(p_{i + 1} - p_i\right)\), that is, the maximum difference between adjacent elements of the sequence p.
Help a classmate find a good index sequence with the maximum width. A classmate promised you that the strings s and t are such that at least one good sequence definitely exists.
Input
The first line of the input contains two numbers n and m (2<=m<=n<=200000) - the lengths of the strings s and t respectively.
The second line of the input contains the string s consisting of lowercase English letters, and the third line contains the string t consisting of lowercase English letters.
It is guaranteed that there is at least one good index sequence.
Output
Print a single number - the maximum width of a good sequence.
Note
In the first example from the condition, there are two good sequences with width 3: these are {1,2,5} and {1,4,5}.
In the second example from the condition, a good sequence of maximum width — this {1,5}.
In the third example, there is only one good sequence from the condition — this {1,2,3,4,5}.
In the fourth example, there is only one good sequence from the condition — this {1,2}.
Examples
| # |
Input |
Output |
| 1 |
5 3
abbbc
abc
|
3
|
| 2 |
5 2
aaaaa
aa
|
4
|
| 3 |
5 5
abcdf
abcdf
|
1
|
| 4 |
2 2
ab
ab
|
1
|