大小为 $n$ 的排列 $p$ 是一个由 $1$ 到 $n$ 的 $n$ 个互不相同的数字组成的序列。我们用 $p(i)$ 表示其中的第 $i$ 个数字。用 $p^k(i)$ 表示 $p(p(p(\dots(p(i))\dots)))$（共 $k$ 次）。如果使得 $p^k(1) = 1$ 的最小正整数 $k$ 等于 $n$，则称该排列为循环排列。

给定一个长度为 $n$ 的字符串 $s$，一个长度为 $m$ 的字符串 $t$，以及一个大小为 $m$ 的循环排列 $p$。你希望 $t$ 成为 $s$ 的一个子串。为此，你可以执行零次或多次“洗牌”（shuffle）操作。洗牌操作是指将 $t$ 替换为 $t'$，使得对于每个 $1 \le i \le m$，原字符串 $t$ 的第 $i$ 个字符等于新字符串 $t'$ 的第 $p(i)$ 个字符。

请判断是否能够通过洗牌操作使 $t$ 成为 $s$ 的一个子串。如果可以，请找出所需的最小洗牌次数。

回想一下，如果存在某个 $l$，满足 $1 \le l \le |s| - |a| + 1$ 且对于每个 $1 \le i \le |a|$ 都有 $s_{l+i-1} = a_i$，则称字符串 $a$ 是 $s$ 的一个子串。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le m \le n \le 200\,000$)。第二行包含 $m$ 个整数 $p(1), \dots, p(m)$：你可以应用的排列。接下来的两行分别包含长度为 $n$ 的字符串 $s$ 和长度为 $m$ 的字符串 $t$。两个字符串均由小写英文字母组成。

题目保证输入的排列是循环排列。

输出格式

如果无法通过洗牌使 $t$ 成为 $s$ 的子串，输出 $-1$。否则，输出获得 $s$ 的子串所需的最小洗牌次数。

样例

输入 1

3 2
2 1
aba
ba

输出 1

0

输入 2

7 4
3 4 2 1
dcabadc
abcd

输出 2

1