A newspaper is published in Walrusland. Its heading is _s_1, it consists of lowercase Latin letters. Fangy the little walrus wants to buy several such newspapers, cut out their headings, glue them one to another in order to get one big string. After that walrus erase several letters from this string in order to get a new word _s_2. It is considered that when Fangy erases some letter, there's no whitespace formed instead of the letter. That is, the string remains unbroken and it still only consists of lowercase Latin letters.
For example, the heading is "_abc_". If we take two such headings and glue them one to the other one, we get "_abcabc_". If we erase the letters on positions 1 and 5, we get a word "_bcac_".
Which least number of newspaper headings _s_1 will Fangy need to glue them, erase several letters and get word _s_2?
## Input
The input data contain two lines. The first line contain the heading _s_1, the second line contains the word _s_2. The lines only consist of lowercase Latin letters (1 ≤ |_s_1| ≤ 104, 1 ≤ |_s_2| ≤ 106).
## Output
If it is impossible to get the word _s_2 in the above-described manner, print "-1" (without the quotes). Otherwise, print the least number of newspaper headings _s_1, which Fangy will need to receive the word _s_2.
[samples]
在海狸国发行一份报纸。其标题为 #cf_span[s1]，由小写拉丁字母组成。小海狸 Fangy 想要购买若干份这样的报纸，剪下它们的标题，按顺序粘贴在一起，形成一个长字符串。之后，海狸会从这个字符串中删除若干个字母，以得到一个新单词 #cf_span[s2]。当 Fangy 删除某个字母时，不会在原位置留下空格，字符串仍然保持连续且仅由小写拉丁字母组成。
例如，标题为 "_abc_"。如果我们取两个这样的标题并将其粘贴在一起，得到 "_abcabc_"。如果我们删除位置 #cf_span[1] 和 #cf_span[5] 上的字母，得到单词 "_bcac_"。
Fangy 最少需要多少个报纸标题 #cf_span[s1]，粘贴后删除若干字母，才能得到单词 #cf_span[s2]？
输入数据包含两行。第一行是标题 #cf_span[s1]，第二行是单词 #cf_span[s2]。这两行仅由小写拉丁字母组成（#cf_span[1 ≤ |s1| ≤ 104, 1 ≤ |s2| ≤ 106]）。
如果无法以所述方式得到单词 #cf_span[s2]，请输出 "-1"（不含引号）。否则，输出 Fangy 为获得单词 #cf_span[s2] 所需的最少报纸标题 #cf_span[s1] 的数量。
## Input
输入数据包含两行。第一行是标题 #cf_span[s1]，第二行是单词 #cf_span[s2]。这两行仅由小写拉丁字母组成（#cf_span[1 ≤ |s1| ≤ 104, 1 ≤ |s2| ≤ 106]）。
## Output
如果无法以所述方式得到单词 #cf_span[s2]，请输出 "-1"（不含引号）。否则，输出 Fangy 为获得单词 #cf_span[s2] 所需的最少报纸标题 #cf_span[s1] 的数量。
[samples]
Let $ s_1 $ and $ s_2 $ be two strings over the alphabet of lowercase Latin letters, with $ |s_1| \geq 1 $, $ |s_2| \geq 1 $.
Define a *subsequence* of a string as a sequence that can be derived from another sequence by deleting some or no elements without changing the order of remaining elements.
We are to find the minimum number $ k \in \mathbb{N} $ such that $ s_2 $ is a subsequence of $ s_1^k $ (i.e., the concatenation of $ s_1 $ repeated $ k $ times).
If $ s_2 $ contains any character not present in $ s_1 $, then no such $ k $ exists; output $ -1 $.
Otherwise, compute the minimal $ k $ such that $ s_2 $ is a subsequence of $ s_1^k $.
Let $ n = |s_1| $, $ m = |s_2| $.
Define a function $ f: \{1, \dots, m\} \to \mathbb{N} $, where $ f(i) $ is the minimal number of copies of $ s_1 $ required to match the prefix $ s_2[1:i] $.
Initialize $ f(0) = 1 $, and for each $ i \in \{1, \dots, m\} $:
- Let $ c = s_2[i-1] $ (0-indexed).
- Find the rightmost occurrence of $ c $ in $ s_1 $ starting from the position after the last matched character in the current copy.
- If $ c \notin s_1 $, return $ -1 $.
- Otherwise, traverse $ s_1 $ cyclically to find the next occurrence of $ c $ after the current position within the current copy; if not found, increment the copy count and restart from the beginning of $ s_1 $.
Formally, simulate a greedy matching of $ s_2 $ over repeated $ s_1 $:
Let $ \text{copies} = 1 $, $ \text{pos} = -1 $ (last matched index in current $ s_1 $, 0-indexed).
For each character $ c \in s_2 $:
- Search for $ c $ in $ s_1 $ starting from index $ \text{pos} + 1 $.
- If found at index $ j \in [\text{pos}+1, n-1] $, set $ \text{pos} = j $.
- Else, search from index $ 0 $ to $ \text{pos} $ (i.e., wrap to next copy), increment $ \text{copies} $, and set $ \text{pos} = j $ where $ j $ is the first occurrence of $ c $ in $ s_1 $.
Return $ \text{copies} $.
**Formal Output:**
Let $ s_1, s_2 \in \Sigma^* $, $ \Sigma = \{a, b, \dots, z\} $.
If $ \text{set}(s_2) \not\subseteq \text{set}(s_1) $, output $ -1 $.
Else, let $ k \in \mathbb{N} $ be the minimal integer such that $ s_2 $ is a subsequence of $ s_1^k $.
Compute $ k $ via greedy traversal:
Initialize $ k = 1 $, $ i = 0 $ (index in $ s_2 $), $ j = -1 $ (last matched index in current $ s_1 $).
While $ i < |s_2| $:
Let $ c = s_2[i] $.
Find the smallest $ p \in \{j+1, j+2, \dots, |s_1|-1\} \cup \{0, 1, \dots, j\} $ such that $ s_1[p] = c $.
If no such $ p \in \{j+1, \dots, |s_1|-1\} $ exists:
$ k \gets k + 1 $, $ j \gets \min \{ p \in [0, |s_1|-1] : s_1[p] = c \} $.
Else:
$ j \gets p $.
$ i \gets i + 1 $.
Output $ k $.
**Final Answer:**
$$
\boxed{
\begin{cases}
-1 & \text{if } \exists c \in s_2 \text{ such that } c \notin s_1 \\
\min \left\{ k \in \mathbb{N} : s_2 \text{ is a subsequence of } s_1^k \right\} & \text{otherwise}
\end{cases}
}
$$