You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

黑客们喜欢在网络上攻击别人的网站，这样可以掠夺他人的私有资产，对他人的财产安全造成巨大危害。所以网络安全专家必须加强防范的手段，不断提升密码的强度。

塔子哥是一个密码破解专家，这一天塔子哥想出了一种名为“冗余覆盖”的密码加密算法。

这是一种基于字符串匹配的加密算法，简单来说就是把密钥字符串 $S1$ 增加 $k$ 个冗余字符然后打乱以后(可能不打乱)加入到一个明文字符串中得到密文字符串 $S2$ ，这个过程叫做 $S2$ 以长度 $k$ 冗余覆盖 $S1$ 。

解读这串密码的方法就是先通过密钥 $[S1,k]$ 去删除 $S2$ 中的冗余子串，这个冗余子串中一定包含 $S1$ 中的所有字符，且每个字符的出现次数一定大于等于在 $S1$ 中的次数。现在需要你编写一个破译系统，它只要根据给定的 $S1$ ， $S2$ ，$k$ ，找出最左侧的 $S2$ 的冗余覆盖 $S1$ 的子串的首个元素的下标，如果没有就返回 $−1$ 。

这样就可以从 $S2$ 中删除冗余子串，并且知道这段密码在说什么。

输入描述

输入第一行为 $S1$ ，输入第二行为 $S2$ ，输入第三行为 $k$ ， $S1$ 和 $S2$ 只包含小写字母.

输出描述

输出最左侧的 $S2$ 以长度 $k$ 冗余覆盖 $S1$ 的子串首个元素下标，如果没有就返回 $-1$ 。

$|S_1|,|S_2| \leq 1e5 , |S_1| + k \leq |S_2|$

样例1

样例输入

ab
cbaaab
1

样例输出

0

样例解释

可以发现最左端的冗余子串是 “cba”，子串中“a”的出现次数为1，“b”的出现次数为1，符合条件。

样例2

样例输入

od
funcode
2

样例输出

2

样例解释

可以发现最左端的冗余子串是 “ncod”，子串中“o”的出现次数为1，“d”的出现次数为1，符合条件。