#include <iostream>
#include <stdlib.h>
#include <time.h>
struct l{int I;l*ll;};void lI(l**l1,int I){l*Il,*II=new l;II->I=I;II->ll=0;if(*
l1){for(Il=*l1;Il->ll;Il=Il->ll);Il->ll=II;}else*l1=II;}void lll(l*l1){for(;l1;
l1=l1->ll)cout<<l1->I<<" ";cout<<"\n";}void ll1(l**l1){l*Il;while(*l1){Il=*l1;*
l1=(*l1)->ll;delete Il;}}void lII(l*l1,l**Il,l**II){int lI1=1;ll1(Il);ll1(II);
for(;l1;l1=l1->ll){lI(lI1?Il:II,l1->I);lI1^=l1->ll&&l1->ll->I<l1->I;}}void Ill(
l**l1,l*Il,l*II){l**lI1;int I;ll1(l1);while(Il||II)for(I=2*!II|!Il;3-I;*lI1=(*
lI1)->ll){lI1=(I&2||(!(I&1)&&Il->I<II->I))?&Il:&II;lI(l1,(*lI1)->I);I|=(!(*lI1)
->ll||(*lI1)->ll->I<(*lI1)->I)*(1+(lI1==&II));}}int main(void){l*l1=0,*Il=0,*II
=0;srand(time(0));for(int IlI=0;IlI<20;IlI++)lI(&l1,rand()%100);lll(l1);do{lII(
l1,&Il,&II);Ill(&l1,Il,II);}while(II);lll(l1);ll1(&l1);ll1(&Il);ll1(&II);return
0;}