F. Mr. Panda and Fantastic Beasts

#include<cstdio>
#include<cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN=400000+10;
const int INF=1e9+7;
int n,k;
int rank[MAXN+1];
int tmp[MAXN+1];
 
//比较（rank[i],rank[i+k]）和(rank[j],rank[j+k])
bool compare_sa(int i,int j){
    if(rank[i]!=rank[j])
        return rank[i]<rank[j];
    else{
        int ri=i+k<=n?rank[i+k]:-1;
        int rj=j+k<=n?rank[j+k]:-1;
        return ri<rj;
    }
}
//rank用来记录字符串的排序，sa用来记录开头字符的位置,S用来记录字符串
//第一个通常是空字符串
//计算字符串S的后缀数组
void construct_sa(string S,int *sa){
    n=S.length();
 
    //初始长度为1，rank直接取字符的编码.
    for(int i=0;i<=n;i++){
        sa[i]=i;
        rank[i]=i<n?S[i]:-1;
    }
 
    //利用对长度为k的排序的结果对长度为2k的排序
    for(k=1;k<=n;k*=2){
        sort(sa,sa+n+1,compare_sa);
 
        //先在tmp中临时储存新计算的rank，再转存回rank中
        tmp[sa[0]]=0;
        for(int i=1;i<=n;i++){
            tmp[sa[i]]=tmp[sa[i-1]]+(compare_sa(sa[i-1],sa[i])?1:0);
        }
        for(int i=0;i<=n;i++){
            rank[i]=tmp[i];
        }
    }
}
 
 
//高度数组lcp的计算
void construct_lcp(string S,int *sa,int *lcp){
    int n=S.length();
    for(int i=0;i<=n;i++) rank[sa[i]]=i;
 
    int h=0;
    lcp[sa[0]]=0;
    for(int i=0;i<n;i++){
        //计算字符串中从位置i开始的后缀及其在后缀数组中的前一个后缀的lcp
        int j=sa[rank[i]-1];
 
        //将h先减去首字母的1长度，在保持前缀相同的前提下不断地增加
        if(h>0) h--;
        for(;j+h<n&&i+h<n;h++){
            if(S[j+h]!=S[i+h]) break;
        }
        lcp[rank[i]-1]=h;
    }
}
 
int sa[MAXN],lcp[MAXN];
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int M[MAXN<<2];
void pushup(int rt){
    M[rt]=min(M[rt<<1],M[rt<<1|1]);
}
void build(int l,int r,int rt){
    if(l==r){
        M[rt]=lcp[l];
        return;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
    if(L<=l&&R>=r){
        return M[rt];
    }
    int m=(l+r)>>1;
    int res=INF;
    if(L<=m)
        res=min(res,query(L,R,lson));
    if(R>m)
        res=min(res,query(L,R,rson));
    return res;
}
string s;
int len;
int ans,fir;
int cas=1;
int pre[MAXN],nxt[MAXN];
void solve(){
    ans=-1,fir=-1;
    memset(pre,0,sizeof pre);
    memset(nxt,0,sizeof nxt);
    int temp=0;
    build(1,n,1);
    for(int i=1;i<=n;i++){
        if(sa[i]>=len){
            temp=i;
        }else{
            pre[i]=temp;
        }
    }
    temp=0;
    for(int i=n;i>=1;i--){
        if(sa[i]>=len){
            temp=i;
        }else{
            nxt[i]=temp;
        }
    }
    for(int i=1;i<=n;i++){
        int MAX=0;
        if(sa[i]<len){
            if(pre[i]){
                MAX=max(MAX,query(pre[i],i-1,1,n,1));
            }
            if(nxt[i]){
                MAX=max(MAX,query(i,nxt[i]-1,1,n,1));
            }
            if((ans==-1||ans>MAX+1)&&sa[i]+MAX+1<=len){
                ans=MAX+1;
                fir=sa[i];
            }
        }
    }
    if(ans==len+1||ans==-1){
        cout<<"Case #"<<cas++<<": Impossible"<<endl;
        return;
    }
    cout<<"Case #"<<cas++<<": ";
    for(int i=fir;i<fir+ans;i++){
        cout<<s[i];
    }
    cout<<endl;
}
 
 
int main()
{
    int t;
    cin>>t;
    while(t--){
        int num;
        cin>>num;
        memset(lcp,0,sizeof lcp);
        memset(sa,0,sizeof sa);
        memset(rank,0,sizeof rank);
        memset(tmp,0,sizeof tmp);
        s="";
        for(int i=0;i<num;i++){
            string temp;
            cin>>temp;
            if(i)
                s+='$';
            else
                len=temp.length();
            s+=temp;
        }
        n=s.length();
        construct_sa(s,sa);
        construct_lcp(s,sa,lcp);
        solve();
    }
}