Yesterday, Mrs. Truong gave Ridiculous Ray a task about strings as part of his ICS3U summative. However, as he did not find the task to be ridiculous enough for his taste, he has decided that you should solve it instead.

The task is as follows:

Ridiculous Ray was given the strings $s$ and $T$, consisting of lowercase English letters. He defines the string $S$ as $s+s+s+\dots$ (infinite) and wants to know the shortest prefix of $S$ that contains $T$ as a subsequence. A string $T$ is a subsequence of a string $S$ if $T$ can be obtained from deleting some characters of $S$ without changing the order of the remaining characters.

Constraints

For all subtasks:

$1\le |s|,|T|\le 5\times {10}^5$

Strings $s$ and $T$ will consist only of lowercase characters.

Note: for any string $x$, $|x|$ is defined as its length.

Subtask 1 [5%]

$1\le |s|,|T|\le 500$

Strings $s$ and $T$ will consist only of the letter a.

Subtask 2 [10%]

$1\le |s|,|T|\le 500$

Subtask 3 [25%]

$1\le |s|,|T|\le 10000$

Subtask 4 [60%]

No additional constraints.

Input Specification

The first line will contain the integers $|s|$ and $|T|$.

The second line will contain $s$.

The third line will contain $T$.

Output Specification

Output the length of the shortest prefix of $S$ that contains $T$ as a subsequence, or -1 if no such prefix exists.

Sample Input 1

6 6
aabbcc
abcabc

Sample Output 1

11

Sample Explanation 1

The length $11$ prefix of $S$ is aabbccaabbc. If we delete the $2^{\text{nd}}$, $4^{\text{th}}$, $6^{\text{th}}$, $8^{\text{th}}$, and ${10}^{\text{th}}$ characters of that prefix, we end up with abcabc, demonstrating that $T$ is a subsequence of that prefix. Additionally, it can be proven that no shorter prefix of $S$ exists that contains $T$ as a subsequence.

Sample Input 2

6 1
abcdef
z

Sample Output 2

-1

Sample Explanation 2

No prefix of $S$ exists that contains $T$ as a subsequence.