Description

To protect the forbidden magic recorded in the spellbook, the author concatenated the magic affixes of spells together without spaces, forming a rune string denoted as $\texttt{S}$.

All magic affixes that make up the rune string are recorded in an even older magic dictionary written by prophets, denoted as $\texttt{T}$. Specifically, all non-empty prefixes of $\texttt{T}$ are valid magic affixes.

Being concise is the top priority when writing a spellbook, so the number of magic affixes used should be as small as possible. Therefore, when deciphering the spellbook, the fewer magic affixes $\texttt{S}$ is split into, the higher the chance that the deciphering is correct.

Cirno wants to know the minimum number of segments when splitting this spellbook into magic affixes.

In particular, if there is no valid splitting scheme, it means this spellbook is fake. Cirno will get a string Fake.

Input Format

The first line contains two integers, representing $|\texttt{T}|$ and $|\texttt{S}|$.

The second line contains a string $\texttt{T}$.

The third line contains a string $\texttt{S}$.

Output Format

Output one line containing an integer or a string Fake, representing the answer.

3 5
aba
abaab

2

3 5
aba
ababa

2

3 5
aba
abbaa

Fake

Hint

Constraints and Notes

For $100\%$ of the testdata, it is guaranteed that $1 \le |\texttt{S}|, |\texttt{T}| \le 10^7$, and $\texttt{S}_x, \texttt{T}_x \in [\texttt{a},\texttt{z}]$.

Subtasks

Subtask 1 ($10$ points): $\texttt{T}_x = \texttt{a}$.

Subtask 2 ($20$ points): $|\texttt{S}| \le 1000$.

Subtask 3 ($30$ points): $|\texttt{S}| \le 10^6$.

Subtask 4 ($40$ points): No special constraints.

Translated by ChatGPT 5