DZY 's BLOG

这么一来我也算一点搞过OI的人了。

这道题也是分层图。k次机会让边权变0。虽然以前搞过但是好久了我也忘了。于是写死写死地写。然后纠结了下标纠结了n久之后就过了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=300000;
const int maxm=7000000;
const int inf=1061109567;
struct HN{
    int x,dis; HN(){}; HN(int _x,int _d):x(_x),dis(_d){};
    inline bool operator < (HN b)const{ return dis<b.dis;}
}H[maxn]; int pos[maxn]={0},size=0; char buf[5000000],*pt=buf; 
int h[maxn],p[maxm],w[maxm],n1[maxm],d[maxn],vis[maxn]={0},tot=0,n,m,K;
inline int getint(){    int r=0;while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;return r;
}inline void sw(int a,int b){
    pos[H[a].x]=b;pos[H[b].x]=a;
    swap(H[a],H[b]);
}void up(int x){
    if(x==1) return;
    if(H[x]<H[x>>1]) sw(x,x>>1),up(x>>1);
}void down(int x){
    int son=x;   if((x<<1)<=size&&H[x<<1]<H[x]) son=x<<1;
    if((x<<1|1)<=size&&H[x<<1|1]<H[son]) son=x<<1|1;
    if(son!=x) sw(x,son),down(son);
}void del(int x){
    sw(x,size); size--; up(x); down(x);
}void ins(HN hn){
    H[++size]=hn; pos[hn.x]=size; up(size);
}inline void ae(int a,int b,int c){
    p[tot]=b; w[tot]=c; n1[tot]=h[a]; h[a]=tot++;
}int dijkstra(int s){
    HN S(s,0),o,tmp;
    size=d[s]=0; ins(S);
    while(size){
        o=H[1]; pos[H[1].x]=0; del(1); //if(o.x==e) return o.dis;
        if(vis[o.x]) continue; vis[o.x]=1;
        for(int i=h[o.x];~i;i=n1[i]) if(!vis[p[i]])
            if(o.dis+w[i]<d[p[i]]){
                d[p[i]]=o.dis+w[i];
                if(pos[p[i]]) {H[pos[p[i]]].dis=d[p[i]];up(pos[p[i]]);}
                else ins(HN(p[i],o.dis+w[i]));
            }
    }return -1;
}int main(){
    fread(pt,1,5000000,stdin); n=getint(); m=getint(); K=getint(); 
    memset(h,0xff,sizeof(h)); memset(d,63,sizeof(d));
    int a,b,c,s=getint(),e=getint();
    for(int i=1;i<=m;i++)a=getint(),b=getint(),c=getint(),ae(a,b,c),ae(b,a,c);
    for(int k=1;k<=K;k++) for(int i=0;i<n;i++) for(int j=h[i];~j;j=n1[j]){
        ae(i+n*k,p[j]+n*k,w[j]);
        ae(i+(k-1)*n,n*k+p[j],0);
    }dijkstra(s);
    printf("%d\n",d[n*K+e]);
    return 0;
}

n个顶点m条边。给你k次机会让边权减半。一次机会对一条边只能做一次。

n、k都是小于50，那么分层。然后就好了。有些细节比较纠结。于是调了好久。囧。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=300000;
const int maxm=7000000;
const int inf=1061109567;
struct HN{
    int x,dis; HN(){}; HN(int _x,int _d):x(_x),dis(_d){};
    inline bool operator < (HN b)const{ return dis<b.dis;}
}H[maxn]; int pos[maxn]={0},size=0; char buf[5000000],*pt=buf; 
int g[55][55]={0},hh[maxn],h[maxn],p[maxm],w[maxm],n1[maxm],d[maxn],vis[maxn]={0},tot=0,n,m,K;
inline int getint(){    int r=0;while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;return r;
}inline void sw(int a,int b){
    pos[H[a].x]=b;pos[H[b].x]=a;
    swap(H[a],H[b]);
}void up(int x){
    if(x==1) return;
    if(H[x]<H[x>>1]) sw(x,x>>1),up(x>>1);
}void down(int x){
    int son=x;   if((x<<1)<=size&&H[x<<1]<H[x]) son=x<<1;
    if((x<<1|1)<=size&&H[x<<1|1]<H[son]) son=x<<1|1;
    if(son!=x) sw(x,son),down(son);
}void del(int x){
    sw(x,size); size--; up(x); down(x);
}void ins(HN hn){
    H[++size]=hn; pos[hn.x]=size; up(size);
}inline void ae(int a,int b,int c){
    p[tot]=b; w[tot]=c; n1[tot]=h[a]; h[a]=tot++;
}int dijkstra(int s){
    HN S(s,0),o,tmp;
    size=d[s]=0; ins(S);
    while(size){
        o=H[1]; pos[H[1].x]=0; del(1); //if(o.x==e) return o.dis;
        if(vis[o.x]) continue; vis[o.x]=1;
        for(int i=h[o.x];~i;i=n1[i]) if(!vis[p[i]])
            if(o.dis+w[i]<d[p[i]]){
                d[p[i]]=o.dis+w[i];
                if(pos[p[i]]) {H[pos[p[i]]].dis=d[p[i]];up(pos[p[i]]);}
                else ins(HN(p[i],o.dis+w[i]));
            }
    }return -1;
}int main(){
    fread(pt,1,5000000,stdin); n=getint(); m=getint(); K=getint(); 
    memset(h,0xff,sizeof(h)); memset(d,63,sizeof(d));
    int a,b,c,s=1,e=n;
    for(int i=1;i<=m;i++)a=getint(),b=getint(),c=getint(),ae(a,b,c),ae(b,a,c);
    memcpy(hh,h,sizeof(h));
    for(int k=1;k<=K;k++) for(int i=1;i<=n;i++) for(int j=hh[i];~j;j=n1[j]){
        ae(i+n*k,p[j]+n*k,w[j]); 
        ae(i+(k-1)*n,n*k+p[j],w[j]>>1);
    }dijkstra(s); int An=inf; for(int i=0;i<=K;i++) An=min(An,d[n*i+e]);
    printf("%d\n",An); return 0;
}

因为求的路径都是从在包含根的一条链上。所以可以考虑直接dfs。记录栈里元素的前缀和。

比如搜到u了，在set里面查询有没有d[u]-k，有的话就加一。然后继续往下dfs的时候把d[u]插入set。

别忘了最开始插个0。

10w个点递归会爆？最好写个手工栈？哈哈我会写了！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
const int maxn=200005;
int n,K,vis[maxn]={0},w[maxn],h[maxn],st[maxn],d[maxn],p[maxn],n1[maxn],tot=0;
set<int>S; char buf[5000000],*pt=buf;
inline int getint(){    int r=0;while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;return r;
}inline void ae(int a,int b){
    p[tot]=b; n1[tot]=h[a]; h[a]=tot++;
    p[tot]=a; n1[tot]=h[b]; h[b]=tot++;
}int main(){
    fread(pt,1,5000000,stdin); n=getint(); K=getint();
    memset(h,-1,sizeof(h)); S.clear(); S.insert(0);
    for(int i=1;i<=n;i++) w[i]=getint(); int u,v,An=0;
    for(int i=1;i<n;i++) u=getint(),v=getint(),ae(u,v);
    int top=0; st[++top]=1; S.insert(w[1]); d[1]=w[1]; vis[1]=1;
    while(top){
        int o=st[top],flag=0;
        for(int i=h[o];~i;i=n1[i]) if(!vis[p[i]]){
            st[++top]=p[i]; h[o]=n1[i]; d[p[i]]=d[o]+w[p[i]];
            vis[p[i]]=flag=1; S.insert(d[p[i]]);
            if(S.find(d[p[i]]-K)!=S.end()) An++;break;
        }if(!flag){ top--; S.erase(d[o]);}
    }printf("%d\n",An); return 0;
}

10000个数。有些数空着给你填。每个数的范围都在1~K内。求出填满后的逆序对的最小值。

很明显这几个填的数是递增的。不然自己就产生逆序对了。（没证明过

先处理出da[i][j]表示i~n中比j大的数，xi[i][j]表示1~i中比j小的数。

f[i][j]表示填到第i个数了，这位填了j所产生的逆序对。

则f[i][j]=min{f[i][k]+da[pos[i]][j]+xi[pos[i]][j]}。然后再加上数列本身的逆序对数就行了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=1061109567;
int a[10005],da[10005][105],xi[10005][105],p[10005],f[10005][100],n,k,m=0,An=0;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(!~a[i]) p[++m]=i;
    }for(int i=2;i<=n;i++){
        for(int j=1;j<=k;j++) da[i][j]=da[i-1][j];
        if(~a[i-1]) for(int j=1;j<a[i-1];j++) da[i][j]++;
    }for(int i=n-1;i;i--){
        for(int j=1;j<=k;j++) xi[i][j]=xi[i+1][j];
        if(~a[i+1]) for(int j=a[i+1]+1;j<=k;j++) xi[i][j]++;
    }for(int i=1;i<=n;i++) if(~a[i]) An+=da[i][a[i]];
    memset(f,63,sizeof(f));
    for(int i=1;i<=k;i++) f[1][i]=da[p[1]][i]+xi[p[1]][i];
    for(int i=2;i<=m;i++) for(int j=1;j<=k;j++) for(int o=1;o<=j;o++)
        f[i][j]=min(f[i][j],f[i-1][o]+da[p[i]][j]+xi[p[i]][j]);
    int An2=inf;  for(int i=1;i<=k;i++) An2=min(An2,f[m][i]);
    An2=(An2==inf)?0:An2;
    printf("%d\n",An+An2); return 0;
}

设dp[i][j]表示第i个数变为j的最小代价。

则dp[i][j]=min{dp[i-1][k]+c*abs(j-k)+(j-h[i])^2}（k是第i-1位上的数，j是当前位上的数）

100000*100*100。。哗~萎掉了。。

把abs(j-k)拆开试试？

j>k时：dp[i][j]=min{dp[i-1][k]+c*j-c*k+(j-h[i])^2}=min{dp[i-1][k]-c*k}+c*j+(j-h[i])^2

j<k时：dp[i][j]=min{dp[i-1][k]+c*k-c*j+(j-h[i])^2}=min{dp[i-1][k]+c*k}-c*j+(j-h[i])^2

那么我们只要在每次转移的时候记录f数组表示min{dp[i-1][k]-c*k}，g数组表示min{dp[i-1][k]+c*k}。这样转移的时候就是O(10w*100)了~

至于空间的话，第一维好像一点用都没有。那就不要了！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define abs(x) (((x)<0)?(-(x)):(x))
#define sqr(x) ((x)*(x))
int dp[105],f[105],g[105],h[100005],n,c;
const int inf=1061109567;
char buf[2000000],*p=buf;
inline int getint(){
    int r=0;while(*p<48||*p>57)p++;while(*p>47&&*p<58)r=r*10+*p++-'0';return r;
}int main(){
    fread(buf,1,2000000,stdin); n=getint(),c=getint();
    for(int i=1;i<=n;i++) h[i]=getint();
    memset(dp,63,sizeof(dp));
    for(int i=h[1];i<=100;i++) dp[i]=sqr(i-h[1]);
    for(int i=2;i<=n;i++){
        f[101]=inf; for(int j=100;j>=1;j--) f[j]=min(dp[j]+j*c,f[j+1]);
        g[0]=inf;   for(int j=1;j<=100;j++) g[j]=min(dp[j]-j*c,g[j-1]);
        memset(dp,63,sizeof(dp));
        for(int j=h[i];j<=100;j++) dp[j]=sqr(j-h[i])+min(g[j]+j*c,f[j]-j*c);
    }int An=inf;
    for(int i=1;i<=100;i++) An=min(An,dp[i]);
    printf("%d\n",An);  return 0;
}

先留一个坑。

题目1：有n堆石子，第i堆有A(i)颗石子。两人依次从中拿取，规定每次只能从一堆中取若干根，可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。

令C=A(1) xor A(2) xor A(3) xor ... xor A(n)，若C>0，则记为利己态，用S表示，若C=0，则记为利他态，用T表示。

【定理1】对于一个S态，一定能从一堆石子中取出若干个，使其成为T态。

【证明】既然是S态，则此时C>0，我们要使得C变为0。

设C转化为二进制后，最高位的1是第p位。那么一定存在一个A(t)的二进制最高位的1是第p位。（显然，不然C的第p位不可能是1）

然后，把第t堆石子的个数变为x=A(t) xor C。因为A(t)和C的二进制最高位的1是同一位。那么异或之后这一位就变成了0。那么x一定小于A(t)。

此时的C'=A(1) xor A(2) xor ... xor A(t) xor C xor A(t+1) xor ... xor A(n)。把C带进去，得到

C'=A(1) xor A(2) xor ... xor A(n) xor A(1) xor A(2) xor ... xor A(n)。显然C'=0。

所以，只要在第t堆石子中取出A(t)-x颗石子，就把S态变为了T态。

【定理2】对于一个T态，从任意一堆取任意个石子出来，都会变为S态。

【证明】用反证法。设此时第i堆的石子数变成了A(i')。此时C=0。如果C'>0，那么命题就成立了。

假设C'=0。则C'=A(1) xor A(2) xor ... xor A(i') xor... xor A(n)=0。

因为C=0。所以C xor C'=0。则A(1) xor A(2) xor ... xor A(i) xor... xor A(n) xor A(1) xor A(2) xor ... xor A(i') xor... xor A(n)=0。

A(i) xor A(i')=0。A(i)=A(i')明显不对了。所以命题得证。

得到了这两个定理之后，我们可以发现，任何一个S态，我们都可以通过自己的控制将它转化成T态。而对方怎么做都是将T态再转回S态，很被动。所以只要先手是S态，总是可以根据定理1得到的策略获胜。

题目2：有n堆石子，第i堆有A(i)颗石子。两人依次从中拿取，规定每次只能从一堆中取若干根，可将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。

再来定义几个状态。一堆石子里只有一个石子，记为孤单堆。否则记为充裕堆。

在T态中，如果充裕堆的个数大于等于2，记为T2态，1个充裕堆，记为T1态，没有充裕堆，记为T0态。S0、S1、S2同理。

【定理3】在S0态中，若孤单堆的个数为奇数。那必输。T0态必赢。

【证明】也就是奇数个石子，每次取一个。很明显先去的人必输。

【定理4】在S1态中，方法正确就必胜。

【证明】如果孤单堆的个数是奇数，那么就把充裕堆取完；如果是偶数，就把充裕堆取的只剩1根。这样留下的就是奇数个孤单堆，对方先手。由定理3得，对方必输，己方必胜。

【定理5】S2态不可一次变为T0态。

【证明】显然，充裕堆不可能一次从2堆以上变为0。

【定理6】S2态可一次变为T2态。

【证明】由定理1得S态可以一次变为T态，而且不会一次取完整堆，那么充裕堆的个数是不会变的，由定理5得S2态不能一次变为T0态，那么转化的T态是T2态。

【定理7】T2态只能转变为S1或S2态。

【证明】由定理2得，T态一次只能变为S态。由于充裕堆数不会变为0。所以是S1或S2态。

【定理8】在S2态中，只要方法正确，就必胜。

【证明】由定理6得，先转化为T2态。由定理7，对方只能再转化回S1或S2态。由定理4，己方必胜。

【定理9】T2态必输。

【证明】同证明8。

我们得到了几个必胜态：S2，S1，T0。必输态：T2，T1，S0。

比较一下两题：

第一题的过程：S2-T2-S2-T2-.....-T2-S1-T0-S0-T0-...-S0-T0（全0）

第二题的过程：S2-T2-S2-T2-.....-T2-S1-S0-T0-S0-...-S0-T0（全0）

我们可以发现前面的过程是一样的。关键在于得到了S1态之后，怎样抉择使自己获胜。而这个是自己可以掌握的。

因此，我们只需要把T2态留给对方，迟早他会转化成S1态。己方就必胜。

HDU 1850

题意：题目1模型。首先判断是否先手必胜。如果必胜则输出第一次的可行方案数。

根据定理1，先得到C的二进制最高位的1是第p位。然后计算n个数中有多少个数最高位的1也是第p位即可。

#include<cstdio>
int a[105];
int main(){
    int n,Xor,t;
    while(scanf("%d",&n),n){
        Xor=0;
        for(int i=1;i<=n;i++)scanf("%d",&a[i]),Xor^=a[i];
        if(!Xor){ printf("0\n"); continue;} 
        int k=0,ans=0; while(Xor)k++,Xor>>=1;
        for(int i=1;i<=n;i++)if(a[i]&(1<<k-1))ans++;
        printf("%d\n",ans);
    }return 0;
}

HDU 1907 

题意：有n堆糖果，每次吃任意一堆中的任意个。可以吃完一堆。不能不吃。吃完最后的负。问先手输赢情况。

很明显就是上面的题目2模型。

#include<cstdio>
int main(){
    int tc; scanf("%d",&tc);
    int n,t;
    while(tc--){
        scanf("%d",&n); int Xor=0,k=0;
        for(int i=1;i<=n;i++) scanf("%d",&t),k+=t>1,Xor^=t;   
        if((Xor&&k>=1)||(!Xor&&!k))printf("John\n");
        else printf("Brother\n");
    }return 0;
}

HDU 2509 也转化为题目2模型。代码大同小异。

模拟一下发现答案与取球的顺序其实是无关的。

然后去膜拜题解发现的确这样。至于证明蒟蒻看不懂。

但是既然这样就是高精度模拟了？

双倍经验（1416 && 1498）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
struct Hugeint{int len,num[10000];  Hugeint(){  len=1;  memset(num,0,sizeof(num));}}An1,An2;
int num[1005],A[10000]={0},B[10000]={0},flag[20005]={0},prime[10000],cnt=0,sum=0;
inline int pre(int n){
    for(int i=2;i<=n;i++){
        if(!flag[i]) prime[cnt++]=i;
        for(int j=0;j<cnt&&prime[j]*i<=n;j++){
            flag[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}inline Hugeint Mul(Hugeint a,Hugeint b){
    Hugeint c;  c.len=a.len+b.len+1;
    for(int i=1;i<=a.len;i++) for(int j=1;j<=b.len;j++)  c.num[i+j-1]+=a.num[i]*b.num[j];
    for(int i=1;i<c.len;i++)  if(c.num[i]>9999) c.num[i+1]+=c.num[i]/10000,c.num[i]%=10000;
    while(c.num[c.len]>9999) c.len++,c.num[c.len]+=c.num[c.len-1]/10000,c.num[c.len-1]%=10000;
    while(c.num[c.len]==0&&c.len>1) c.len--;   return c;
}inline Hugeint pow(int b,int p){
    Hugeint ans,bb; ans.len=bb.len=ans.num[1]=1ll;  bb.num[1]=b;
    while(p){if(p&1ll)ans=Mul(ans,bb);p>>=1ll;bb=Mul(bb,bb);}   return ans;
}void print(Hugeint a){
    printf("%d",a.num[a.len]); for(int i=a.len-1;i;i--)printf("%04d",a.num[i]);
}inline void pushA(int k){
    for(int i=0;k>1&&i<cnt&&prime[i]<=k;i++) while(k%prime[i]==0)A[i]++,k/=prime[i];
}inline void pushB(int k){
    for(int i=0;k>1&&i<cnt&&prime[i]<=k;i++) while(k%prime[i]==0)B[i]++,k/=prime[i];
}int main(){
    int n,m,d,x,y;  pre(20000);
    scanf("%d%d%d",&n,&m,&d); for(int i=1;i<=n;i++)scanf("%d",&num[i]),sum+=num[i];
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        if(num[y]==0){ printf("0/1\n");return 0;}
        pushA(num[y]);  pushB(sum);
        num[y]+=d;      sum+=d;
    }for(int i=0;i<cnt;i++) if(A[i]&&B[i]){
        if(A[i]>B[i])   A[i]-=B[i], B[i]=0;
        else            B[i]-=A[i], A[i]=0;
    }An1.num[1]=An2.num[1]=1;
    for(int i=0;i<cnt;i++)  if(A[i])    An1=Mul(An1,pow(prime[i],A[i]));
    for(int i=0;i<cnt;i++)  if(B[i])    An2=Mul(An2,pow(prime[i],B[i]));
    print(An1);putchar('/');print(An2);putchar('\n');return 0;
}

给你一颗无根树。每条边的路径长是1。

每次询问给你三个点。要求你找到一个点。使其它三个点到这个点的路径和最小。

看到这种题就很快联想到LCA了。然后看看样例然后随便手造几组数据，发现求的点一定在其中两个点的LCA。

那么就好了。每次求出3个LCA。然后枚举。算出距离和。

介于倍增比rmq好写的多。就没写rmq。不过倍增的话每次求lca是logn的。每次询问差不多要做6次LCA。那么6logn。

如果是rmq的话每次询问时O(1)。预处理都是nlogn。那么常数一下就跪了。刷rank1也没戏了、不过还有个rank2= =还是玩不过seter、、跪烂、、

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char buf[21000000],*pt=buf,*o=buf;
int p[1000005],n1[1000005],h[500005]={0},q[500005],d[500005],v[500005]={0};
int lg[500005],a[500005][20],n,m,tot=1;
inline int getint(){    int r=0; while(*pt<48||*pt>57)pt++;
    while(*pt>47&&*pt<58)r=r*10+*pt++-48; return r;
}inline void print(int x){
    char str[11],*p=str; if(!x)*o++=48;
    else{ while(x) *p++=x%10+48,x/=10; while(p--!=str)*o++=*p;}
}inline void ae(int a,int b){
    p[tot]=b; n1[tot]=h[a]; h[a]=tot++; p[tot]=a; n1[tot]=h[b]; h[b]=tot++;
}inline void pre(){
    int s=0,e=1; q[0]=1; d[1]=1; v[1]=1;
    while(s<e){
        for(int i=h[q[s++]];i;i=n1[i]) if(!v[p[i]])
            v[p[i]]=1,q[e++]=p[i],d[p[i]]=d[q[s-1]]+1,a[p[i]][0]=q[s-1];
    }for(int j=1;j<20;j++) for(int i=1;i<=n;i++) a[i][j]=a[a[i][j-1]][j-1];
}inline int lca(int u,int v){
    if(d[u]>d[v]){ u^=v; v^=u; u^=v;}
    int k=d[v]-d[u],j=0; while(k){ if(k&1)v=a[v][j]; j++; k>>=1;}
    if(u==v)return u;
    for(int i=lg[d[u]-1];~i;i--)
        if(a[u][i]!=a[v][i]) u=a[u][i],v=a[v][i];
    return a[u][0]; 
}int main(){
    fread(pt,1,21000000,stdin);  
    n=getint();m=getint();
    for(int i=0;(1<<i)<=n;i++)
        for(int j=(1<<i);j<(1<<i+1)&&j<=n;j++)lg[j]=i;
    int u,v,w,a1,a2,a3,a4,a5,An1,An2;
    for(int i=1;i<n;i++) u=getint(),v=getint(),ae(u,v); 
    pre();
    for(int i=1;i<=m;i++){
        u=getint(),v=getint(),w=getint();
        a1=lca(u,v),a2=lca(u,w),a3=lca(v,w),a4=d[u]+d[v]+d[w];
        An1=a1,An2=a4-d[a1]-(d[lca(w,a1)]<<1);
        if((a5=a4-d[a2]-(d[lca(v,a2)]<<1))<An2) An2=a5,An1=a2;
        if((a5=a4-d[a3]-(d[lca(u,a3)]<<1))<An2) An2=a5,An1=a3;
        print(An1);*o++=' ';print(An2);*o++='\n';
    }return fwrite(buf,1,o-buf,stdout),0;
}