Longest Decomposable Prefix

In biology, the structure of certain organisms is represented by a sequence of uppercase letters. Biologists are interested in decomposing long sequences into shorter substrings, called elements. Given a set \( P \) and a sequence \( s \) (consisting of uppercase letters), we say that \( s \) can be decomposed into elements of \( P \) if there exists a sequence of elements (elements may be reused and not all elements need to appear) whose concatenation equals \( s \). For example, the sequence ABABACABAAB can be decomposed using the set \( P = \{A,\; AB,\; BA,\; CA,\; BBC\} \).

The first \( k \) characters of \( s \) form a prefix of length \( k \). Your task is to determine the length \( k \) of the longest prefix \( s' \) of \( s \) for which there exists a segmentation into one or more elements from \( P \). In other words, find the maximum \( k \) (with \( 0 \le k \le |s| \)) such that \( s[0:k] \) can be segmented into elements from \( P \). All formulas are given in LaTeX format, e.g., \( \le \) and \( |s| \).

inputFormat

The input consists of three lines:

1. An integer \( n \) representing the number of elements in the set \( P \).
2. \( n \) uppercase letter strings separated by spaces representing the elements of \( P \).
3. A string \( s \) composed of uppercase letters.

outputFormat

Output a single integer \( k \), the length of the longest prefix of \( s \) that can be decomposed into elements from \( P \).

sample

5
A AB BA CA BBC
ABABACABAAB

11