#include<bits/stdc++.h>
using namespace std;
int n;
int x[15]; 
bool dfs(int now,int dep){
    if(now>dep)return 0;
    bool vis[310];
    for(int i=now-1;i>=1;i--){
        for(int j=now-1;j>=1;j--){
            if(!vis[x[i]+x[j]]){
                vis[x[i]+x[j]]=1;
                x[now]=x[i]+x[j];
                if(x[now]<=x[now-1] || x[now]>n)continue;
                if(x[now]==n)return 1;
                if(dfs(now+1,dep))return 1;
                vis[x[i]+x[j]]=0;
            }
        }
    }
    return 0;
}
int main(){
    while(scanf("%d",&n)==1 && n){
        if(n==1)printf("1   1\n");
        else if(n==2)printf("2   1 2\n");
        else{
            for(int i=3;i<=10;i++){
                x[1]=1,x[2]=2;
                if(dfs(3,i)==1){
                    printf("%d   ",i);
                    for(int j=1;j<=i;j++)printf("%d ",x[j]);
                    printf("\n");
                    break;
                }
            }
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
char s[1010][1010],t[1010][1010];
ull h1[1010][1010];
ull h2[1010][1010];
ull pow131[1010];
ull pow233[1010];
int n,m,a,b;
multiset<ull> mul;
void ghs(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            h1[i][j]=h1[i-1][j]*131+s[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            h1[i][j]=h1[i][j]+h1[i][j-1]*233;
        }
    }
}
int main(){
    scanf("%d%d%d%d",&n,&m,&a,&b);
    memset(h1,0,sizeof(h1));
    pow131[0]=pow233[0]=1;
    for(int i=1;i<=n;i++){
        scanf("%s",s[i]+1);
        pow131[i]=pow131[i-1]*131;
        pow233[i]=pow233[i-1]*233;
    }
    ghs();
    for(int i=1;i<=n-a+1;i++){
        for(int j=1;j<=m-b+1;j++){
            ull x=h1[i+a-1][j+b-1];
            x-=(h1[i-1][j+b-1]*pow131[a]);
            x-=(h1[i+a-1][j-1]*pow233[b]);
            x+=(h1[i-1][j-1]*pow131[a]*pow233[b]);
            mul.insert(x);
        }
    }
    int q;
    scanf("%d",&q);
    while(q--){
        for(int i=1;i<=a;i++)scanf("%s",t[i]+1);

        for(int i=1;i<=a;i++){
            for(int j=1;j<=b;j++){
                h2[i][j]=h2[i-1][j]*131+t[i][j];
            }
        }
        for(int i=1;i<=a;i++){
            for(int j=1;j<=b;j++){
                h2[i][j]=h2[i][j]+h2[i][j-1]*233;
            }
        }
        ull ts=h2[a][b];
        multiset<ull>::iterator it=mul.find(ts);
        if(it==mul.end())printf("0\n");
        else printf("1\n");
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int a[100010],b[130],cnt[5];
int f[45][45][45][45];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=m;i++){
        scanf("%d",&b[i]);
        cnt[b[i]]++;
    }
    f[0][0][0][0]=a[1];
    for(int i=0;i<=cnt[1];i++){
        for(int j=0;j<=cnt[2];j++){
            for(int k=0;k<=cnt[3];k++){
                for(int l=0;l<=cnt[4];l++){
                    if(i==j && j==k && k==l && i==0)continue;
                    int pos=i*1+j*2+k*3+l*4+1;
                    if(i!=0)f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+a[pos]);
                    if(j!=0)f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+a[pos]);
                    if(k!=0)f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+a[pos]);
                    if(l!=0)f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+a[pos]);
                }
            }
        }
    }
    printf("%d",f[cnt[1]][cnt[2]][cnt[3]][cnt[4]]);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0x3f3f3f3f;
int a[310][310],d[310][310],pos[310][310];
vector<int> path;
void get_path(int x,int y){
    if(pos[x][y]==0)return ;
    get_path(x,pos[x][y]);
    path.push_back(pos[x][y]);
    get_path(pos[x][y],y);
}
int main(){
    scanf("%d%d",&n,&m);
    memset(a,0x3f,sizeof(a));
    for(int i=1;i<=n;i++)a[i][i]=0;
    while(m--){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        a[y][x]=a[x][y]=min(a[x][y],z);
    }
    memcpy(d,a,sizeof(a));
    for(int k=1;k<=n;k++){
        for(int i=1;i<k;i++){
            for(int j=i+1;j<k;j++){
                if((long long)d[i][j]+a[j][k]+a[k][i]<ans){
                    ans=d[i][j]+a[j][k]+a[k][i];
                    path.clear();
                    path.push_back(i);
                    get_path(i,j);
                    path.push_back(j);
                    path.push_back(k);
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(d[i][j]>d[i][k]+d[k][j]){
                    d[i][j]=d[i][k]+d[k][j];
                    pos[i][j]=k;
                }
            }
        }
    }
    if(ans==0x3f3f3f3f){
        puts("No solution.");
        return 0;
    }
    for(int i=0;i<path.size();i++){
        printf("%d ",path[i]);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int res[210][210],k,m,S,E,n,g[210][210];
map<int,int> id;
void mul(int c[][210],int a[][210],int b[][210]){
    int tmp[210][210];
    memset(tmp,0x3f3f3f,sizeof(tmp));
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++)tmp[i][j]=min(tmp[i][j],a[i][k]+b[k][j]);
        }
    }
    memcpy(c,tmp,sizeof(tmp));
}
void ksm(){
    memset(res,0x3f3f3f,sizeof(res));
    for(int i=1;i<=n;i++)res[i][i]=0;
    while(k){
        if(k&1)mul(res,res,g);
        mul(g,g,g);
        k>>=1;
    }
}
int main(){
    cin>>k>>m>>S>>E;
    memset(g,0x3f,sizeof(g));
    if(!id.count(S)) id[S]=++n;
    if(!id.count(E)) id[E]=++n;
    S=id[S],E=id[E];
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&c,&a,&b);
        if(!id.count(a)) id[a]=++n;
        if(!id.count(b)) id[b]=++n;
        a=id[a],b=id[b];
        g[a][b]=g[b][a]=min(g[a][b],c);
    }
    ksm();
    cout<<res[S][E]<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int dis[30][30];
pair<int,int> ans[30];
int n,m;
void floyd(int x){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dis[i][j]=min(dis[i][j],dis[i][x]+dis[x][j]);
        }
    }
}
bool check(){
    for(int i=1;i<=n;i++){
        int cnt=0;
        for(int j=1;j<=n;j++)if(dis[i][j]!=1e9)cnt++;
        ans[i]={cnt,i};
        for(int j=1;j<=n;j++)if(i!=j && dis[j][i]!=1e9)cnt++;
        if(cnt!=n)return 0;
    }
    sort(ans+1,ans+1+n);
    return 1;
}
int main(){
    while(scanf("%d%d",&n,&m)==2 && n){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++)if(i!=j)dis[i][j]=1e9;
        }
        int flag=0;
        for(int t=1;t<=m;t++){
            string s;
            cin>>s;
            int x=s[0]-'A'+1,y=s[2]-'A'+1;
            if(s[1]=='>')swap(x,y);
            if(!flag && dis[x][y]!=1e9){
                printf("Inconsistency found after %d relations.\n",t);
                flag=1;
            }
            dis[y][x]=1;
            floyd(x);floyd(y);
            if(!flag && check()){
                printf("Sorted sequence determined after %d relations: ",t);
                for(int i=1;i<=n;i++)printf("%c",ans[i].second+'A'-1);
                printf(".\n");
                flag=1;
            }
        }
        if(!flag)printf("Sorted sequence cannot be determined.\n");
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int a[10][10];
int v1[10][10],v2[10][10],v3[10][10];
int ans=-1;
int s[10][10]={
0,0,0,0,0,0,0,0,0,0,
0,6,6,6,6,6,6,6,6,6,
0,6,7,7,7,7,7,7,7,6,
0,6,7,8,8,8,8,8,7,6,
0,6,7,8,9,9,9,8,7,6,
0,6,7,8,9,10,9,8,7,6,
0,6,7,8,9,9,9,8,7,6,
0,6,7,8,8,8,8,8,7,6,
0,6,7,7,7,7,7,7,7,6,
0,6,6,6,6,6,6,6,6,6,
};
int score(){
    int sum=0;
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++)sum+=s[i][j]*a[i][j];
    }
    return sum;
}
void dfs(int x,int y){
    if(x<1){
        ans=max(ans,score());
        return ;
    }
    int z=(x-1)/3*3+(y-1)/3+1;
    if(a[x][y]){
        if(y==1)dfs(x-1,9);
        else dfs(x,y-1);
        return ;
    }
    for(int i=9;i>=1;i--){
        if(!v1[x][i] && !v2[y][i] && !v3[z][i]){
            a[x][y]=i;
            v1[x][i]=v2[y][i]=v3[z][i]=1;
            if(y==1)dfs(x-1,9);
            else dfs(x,y-1);    
            v1[x][i]=v2[y][i]=v3[z][i]=0;   
            a[x][y]=0;
        }
    }
}
int main(){
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            scanf("%d",&a[i][j]);
            if(a[i][j]){
                int z=(i-1)/3*3+(j-1)/3+1;
                v1[i][a[i][j]]=v2[j][a[i][j]]=v3[z][a[i][j]]=1;
            }
        }
    }
    dfs(9,9);
    printf("%d",ans);
    return 0;
} 

#include<bits/stdc++.h>
using namespace std;
int mxr[20010],mxh[20010];
int ans=1e8;
int n,m;
void dfs(int now,int s,int v,int lh,int lr){
    if(now==0){
        if(v==n)ans=min(ans,s);
        return ;
    }
    if(s+2*(n-v)/lr>ans)return ;
    if(s+mxr[now]>ans || v+mxh[now]>n)return ;
    for(int i=lr-1;i>=now;i--){
        if(now==m)s=i*i;
        int maxh=min(lh-1,(n-v-mxh[now-1])/(i*i));
        for(int j=maxh;j>=now;j--){
            dfs(now-1,s+2*i*j,v+i*i*j,j,i);
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        mxr[i]=mxr[i-1]+2*i*i;
        mxh[i]=mxh[i-1]+i*i*i;
    }
    dfs(m,0,0,n,int(sqrt(n)));
    if(ans==1e8)ans=0;
    printf("%d",ans);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y,z;
}edge[6010];
int fa[6010],s[6010];
long long ans;
bool operator <(node a,node b){
    return a.z<b.z;
}
int get(int x){
    if(x==fa[x])return x;
    return fa[x]=get(fa[x]);
}
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<n;i++){
            scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);
            fa[i]=i;
            s[i]=1;
        }
        fa[n]=n,s[n]=1;
        sort(edge+1,edge+n);
        ans=0;
        for(int i=1;i<n;i++){
            int tx=get(edge[i].x);
            int ty=get(edge[i].y);
            if(tx==ty)continue;
            ans+=1ll*(edge[i].z+1)*(s[tx]*s[ty]-1);
            fa[tx]=ty;
            s[ty]+=s[tx];
        }
        cout<<ans<<endl;
    }
}

#include<bits/stdc++.h>
using namespace std;
int n,m;
int price[100010];
int h[100010],rh[100010],e[2000010],ne[2000010],idx;
int dmin[100010],dmax[100010];
bool vis[100010];
void add(int *h,int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void spfa(int *d,int start,int *h,bool flag){
    queue<int> q;
    memset(vis,0,sizeof(vis));
    if(flag)memset(d,0x3f,sizeof(dmin));
    q.push(start);
    vis[start]=true;
    d[start]=price[start];
    while(q.size()){
        int t=q.front();
        q.pop();
        vis[t]=false;
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if (flag && d[j]>min(d[t],price[j]) || !flag && d[j]<max(d[t],price[j])){
                if(flag)d[j]=min(d[t],price[j]);
                else d[j]=max(d[t],price[j]);
                if(!vis[j]){
                    vis[j]=true;
                    q.push(j);
                }
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof(h));
    memset(rh,-1,sizeof(rh));
    for(int i=1;i<=n;i++)scanf("%d",&price[i]);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(h,a,b),add(rh,b,a);
        if(c==2)add(h,b,a),add(rh,a,b);
    }
    spfa(dmin,1,h,true);
    spfa(dmax,n,rh,false);
    int res=0;
    for(int i=1;i<=n;i++)res=max(res,dmax[i]-dmin[i]);
    printf("%d\n",res);
    return 0;
}