#include<stdio.h>
#include<stdlib.h>
typedef struct _polynomial* Polynomial;
typedef struct _polynomial* Item;
struct _polynomial{
int e;
int x;
Item next;
};
Item NewItem(int e,int x);
Polynomial Read_Poly();
void Print_Poly(Polynomial p);
Polynomial Add_Poly(Polynomial p1,Polynomial p2);
Polynomial Multi_Poly(Polynomial p1,Polynomial p2);
int main(){
Polynomial p1,p2;
p1 = Read_Poly();
p2 = Read_Poly();
Print_Poly( Multi_Poly( p1,p2 ));
Print_Poly( Add_Poly(p1,p2));
free(p1); free(p2);
return 0;
}
Polynomial Read_Poly(){
int t;
int x,e;
Polynomial p,pnew,phead;
phead = (Polynomial) malloc(sizeof(struct _polynomial));
p = phead;
scanf("%d",&t);
if( t == 0) return NULL;
while( t--){
scanf("%d %d",&x,&e);
pnew = (Polynomial ) malloc(sizeof(struct _polynomial));
pnew->e = e;
pnew->x = x;
pnew->next = NULL;
p->next = pnew;
p = pnew;
}
p = phead;
phead = phead->next;
free(p);
return phead;
}
void Print_Poly(Polynomial p) {
Item i = p;
int tag = 1;
if( p == NULL) {
printf("0 0\n");
return ;
}
while( i){
if( tag == 0) putchar(' ');
else tag=0;
printf("%d %d",i->x,i->e);
i = i->next;
}
putchar('\n');
}
Polynomial Add_Poly(Polynomial p1,Polynomial p2){
Polynomial res;
Item i1,i2,pnew,p;
i1 = p1; i2 = p2;
res = (Polynomial) malloc( sizeof( struct _polynomial));
res->next = NULL;
p = res;
while( i1 && i2){
if( i2->e > i1->e) {
pnew = NewItem(i2->e,i2->x);
p->next = pnew;
p = pnew;
i2=i2->next;
}
else if( i1->e > i2->e) {
pnew = NewItem(i1->e,i1->x);
p->next = pnew;
p = pnew;
i1=i1->next;
}
else {
if( i1->x + i2->x != 0){
pnew = NewItem(i2->e,i1->x + i2->x );
p->next = pnew;
p = pnew;
}
i1 = i1->next; i2 = i2->next;
}
}
while( i1) {
pnew = NewItem(i1->e,i1->x);
p->next = pnew;
p = pnew;
i1=i1->next;
}
while( i2){
pnew = NewItem(i2->e,i2->x);
p->next = pnew;
p = pnew;
i2 = i2->next;
}
pnew = res;
res = res->next;
free(pnew);
return res;
}
Item NewItem(int e,int x){
Item i = (Item) malloc(sizeof(struct _polynomial));
i -> e = e;
i -> x = x;
}
Polynomial Multi_Poly(Polynomial p1, Polynomial p2){
Item i1,i2;
Polynomial res,p,pr,pnew;
res = NULL;
i1 = p1;
while( i1 ){
pr = (Polynomial) malloc( sizeof( struct _polynomial));
p = pr;
i2 = p2;
while( i2) {
pnew = NewItem(i1->e+i2->e, i1->x * i2->x);
p->next = pnew;
p = pnew;
i2 = i2->next;
}
p = pr; pr = pr->next; free(p);
res = Add_Poly(res,pr);
free(pr);
i1 = i1->next;
}
return res;
}