Gym - 101466E ​​​​​​​ Text Editor（KMP求子串出现次数 + 二分大法）

Text Editor

One of the most useful tools nowadays are text editors, their use is so important that the Unique Natural Advanced Language (UNAL) organization has studied many of the benefits working with them.

They are interested specifically in the feature "find", that option looks when a pattern occurs in a text, furthermore, it counts the number of times the pattern occurs in a text. The tool is so well designed that while writing each character of the pattern it updates the number of times that the corresponding prefix of the total pattern appears on the text.

Now the UNAL is working with the editor, finding patterns in some texts, however, they realize that many of the patterns appear just very few times in the corresponding texts, as they really want to see more number of appearances of the patterns in the texts, they put a lower bound on the minimum number of times the pattern should be found in the text and use only prefixes of the original pattern. On the other hand, the UNAL is very picky about language, so they will just use the largest non-empty prefix of the original pattern that fit into the bound.

Input

The first line contains the text A (1 ≤ |A| ≤  105) The second line contains the original pattern B (1 ≤ |B| ≤  |A|) The third line contains an integer n (1 ≤ n ≤  |A|) - the minimum number of times a pattern should be found on the text.

Output

A single line, with the prefix of the original pattern used by the UNAL, if there is no such prefix then print "IMPOSSIBLE" (without the quotes)

Examples

Input

aaaaa
aaa
4

Output

aa

Input

programming
unal
1

Output

IMPOSSIBLE

Input

abracadabra
abra
1

Output

abra

Input

Hello World!
H W
5

Output

IMPOSSIBLE

题意：给定两个字符串 s ，和 t ，还有一个整数 k ，要求一个 t 中的前缀子串，要求 这个前缀子串在 s 中出现的次数 至少是 k ，且字符串尽量长。

思路：KMP 求 子串出现次数模版 + 二分 前缀。 对于每个 二分 得到的 mid 前缀，如果 这个 mid 前缀出现的次数  < k, r 就减小，否则 l 增大。

AC代码：

#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 1e5 + 10;
int next[maxn];
char s[maxn],t[maxn];

void getnext(int lent){
    int i = 0,j = -1;
    next[i] = -1;
    while(i < lent){
        if(j == -1 || t[i] == t[j]){
            i ++ ;j ++;
            next[i] = j;
        }
        else j = next[j];
    }
}

int kmp_count(int lens,int lent){
    getnext(lent);
    int i = 0,j = 0,ans = 0;
    while(i < lens){
        if(j == -1 || s[i] == t[j])
            i ++,j ++;
        else j = next[j];
        if(j == lent){
            ans ++;
            j = next[j-1];
            i --;
        }
    }
    return ans;
}

int main()
{
    gets(s);
        gets(t);
        int k; scanf(" %d",&k);
        char tmp[maxn];
        int lens = strlen(s);
        int lent = strlen(t);

        int l = 0,r = lent,mid;
        int ans = 0;
        while(l <= r){
            mid = (l + r) >> 1;
            for(int i = 0;i < mid;i ++)
                tmp[i] = t[i];
                //cout << tmp << endl;
                //cout << mid << endl;
            if(mid == 0) break;
            if(kmp_count(lens,mid) < k){
                r = mid - 1;
            }
            else ans = mid, l = mid + 1;
        }
        if(mid == 0) printf("IMPOSSIBLE");
        else {
            for(int i = 0;i < ans;i ++)
                printf("%c",tmp[i]);
        }
        printf("\n");
    return 0;
}