//高精度四位压缩================================================
const int M=85,mod=10000;
struct HP {
    int p[505],len;
    HP() {
        memset(p,0,sizeof(p));
        len=0;
    }//初始化一个高精度变量
    void put_out() { //输出
        printf("%d",p[len]);
        for(int i=len-1; i>0; i--) {
            if(p[i]==0) {
                printf("0000");
                continue;
            }
            for(int k=10; k*p[i]<mod; k*=10)printf("0");
            printf("%d",p[i]);

        }
    }
} f[M][M],base[M],ans;
//高精+高精 O(len)
HP operator + (const HP &a,const HP &b) {
    HP c;
    c.len=max(a.len,b.len);
    int x=0;
    for(int i=1; i<=c.len; i++) {
        c.p[i]=a.p[i]+b.p[i]+x;
        x=c.p[i]/mod;
        c.p[i]%=mod;
    }
    if(x>0)c.p[++c.len]=x;
    return c;
}
//高精*单精 O(len)
HP operator * (const HP &a,const int &b) {
    HP c;
    c.len=a.len;
    int x=0;
    for(int i=1; i<=c.len; i++) {
        c.p[i]=a.p[i]*b+x;
        x=c.p[i]/mod;
        c.p[i]%=mod;
    }
    while(x>0) {
        c.p[++c.len]=x%mod;
        x/=mod;
    }
    return c;
}
//max 高精
HP max (const HP &a,const HP &b) {
    if(a.len>b.len)
        return a;
    if(a.len<b.len)
        return b;
    for(int i=a.len; i>0; i--) {
        if(a.p[i]>b.p[i])
            return a;
        if(a.p[i]<b.p[i])
            return b;
    }
    return a;
}
//================================================