# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# 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**and

_{2}**S**(1 ≤ Length of S

_{3}_{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 S 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 S Another palindromic substring of S |

Input | Output |
---|---|

3 bcbaaaaa bb cb | 0 |

Here, the optimal palindromic substring of S |

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”.

Login to submit