A38505.串串

夏天到了，又到了吃串串的季节。

你的手中有两个串串。每个串串上都串了很多食材。

如果把串串上的食材看成字符，那么一个串串就相当于由一些字符组成的字符串。为了方便描述，我们把这两个串串称作字符串$A$和$B$。

现在，你想找到字符串$B$的一个最长前缀，使得这个前缀在字符串$A$中至少出现了$n$次($n\leq |A|$)。

这$n$次出现可以重叠，例如在字符串"ababa"中，"aba"出现了两次。

第一行一个字符串$A$，只包含英文小写字母。

第二行一个字符串$B$，只包含英文小写字母。

第三行一个整数$n$，意义如题。

输出一共一行。

如果存在$B$的最长前缀，使得这个前缀在$A$中至少出现了$n$次，则输出这个最长前缀；

否则，输出"IMPOSSIBLE"(不含引号)。

【数据范围】

对于前$30\%$数据，$1 \leq |B| \leq |A| \leq 300$；

对于前$60\%$数据：$1 \leq |B| \leq |A| \leq 5000$；

对于$100\%$的数据，$1 \leq |B| \leq |A| \leq 10^5$，$1 \leq n\leq |A|$。