You are given a string S of length N$.$ You are also given a string array str of size M$.$

It is given that a string X is beautiful if there is a subsequence concatenation K from the string array str that meets the following conditions:

$1)$ The length of K is equal to the length of X$.$

$2)$ The concatenation of K and the string X is a palindrome string.

This means if str $=["$a$","$b$","$dc$"],$ X $=$ "cda" then we can take the subsequence $"$a$","$dc$"$ from str and concatenate them to get K$=$ "adc". The length of "adc" is equal to the length of X and their concatenation is a palindrome string

Find the longest prefix length from S that can be divided into beautiful substrings.

Notes:

$1)$ It is given that a string is a palindrome string if reading it from left to right is equal to reading it from right to left.

Input Format

$1)$ The first line contains an integer,N$,$ denoting the length of string S$.$

$2)$ The next line contains an integer, M$,$ denoting the size of the string array str$.$

$3)$ The next line contains a string S$,$ denoting the given string.

$4)$ Each line i of the M subsequent lines $($where $0<=$ i $<$ M$)$ contains a string describing str$[$i$].$

input: n$=5,$ m$=3,$ S$=$"abcda", str$=["$a$","$b$","$dc$"]$

output: $5$