Zoba the Misleader

Zoba has 3 strings, named $S_1$, $S_2$ and $S_3$. He wanted to make a tough problem for Mihaf with these strings.

Zoba said to Mihaf, "Here is a challenge for you. You have to find a palindromic substring from $S_1$ in such a way that the length of this substring is maximum and an odd number greater than one. The number of unique characters in this substring must be at least K. After removing the character in middle of this substring, the new even-length palindromic substring must be a substring of string $S_2$. Furthermore, the last half of this new substring also must be a substring of $S_3$. Mihaf, you have to tell the length of the palindromic substring from $S_1$ that will satisfy all these constraints. If fail to do so, you will have to pay the bill of my dinner tonight. And if you succeed, my bill of tonight's dinner will be paid by you. Are you up for it?"

Mihaf thinks that he can easily win this challenge by coming to you, a great programmer who will write a code to find the answer for Mihaf. Can you do this?

Input

At the first line of input, you will be given an integer $K$ ($1 ≤ K ≤ 26$), its description is in the problem statement.

Then each of the next 3 lines, the strings $S_1$, $S_2$ and $S_3$ ($1 ≤ |S_1|, |S_2|, |S_3| ≤ 10^6$) are given one by one. The characters in each of these strings are lowercase Latin letters.

Output

Find the length of the palindromic substring of $S_1$ which satisfies the constraints of the problem description. If no such substring exists, print 0.

Samples

Input	Output
1 bcbaaaaa bb cb	3
Here, the optimal palindromic substring of S1 is bcb. The number of unique characters in it is 2, which is larger than K. When the middle character c is removed, it becomes bb, a palindromic substring of S2. Its last half is b, a substring of string S3. Another palindromic substring of S1 is aaaaa which is not valid as aaaa is not a substring of S2.

Input	Output
3 bcbaaaaa bb cb	0
Here, the optimal palindromic substring of S1 is none since there is no palindromic substring of S1 where the number of unique characters is at least k=3.

A substring is a contiguous sequence of characters within a string. For instance, "the best of" is a substring of "It was the best of times".