Input format:

The input is divided into two lines. Each line gives the number of nonzero terms of polynomials, and then enters a coefficient and index of nonzero terms of polynomials (the absolute value is not more than 1000 integers) in exponential descending mode. Numbers are separated by spaces.

Output format:

The output is divided into two lines. The product polynomials and the coefficients and exponents of the nonzero terms of the sum polynomials are output exponentially. Numbers are separated by spaces, but no extra spaces are allowed at the end. Zero polynomial should output 0 0.

Input example:

4 3 4 -5 2  6 1  -2 0
3 5 20  -7 4  3 1

Output example:

15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0

Finally, the code is as follows:

#include <stdio.h>
#include <stdlib.h>

typedef struct PolyNode *Polynomial;
struct PolyNode {
    int coef;
    int expon;
    Polynomial link; 
};

void Attach(int c,int e,Polynomial *pRear) {
    Polynomial P;
    P=(Polynomial)malloc(sizeof(struct PolyNode));
    P->coef=c;
    P->expon=e;
    P->link=NULL;
    (*pRear)->link=P; /*P The new node pointed to is inserted after the current Trailer*/
    *pRear=P;   /*pRear Pointer moves to P node*/
}

int Compare(int a,int b){
    int c;
    if (a>b) c=1;
    else if (a<b) c=-1;
    else c=0;
    return c;
}

Polynomial ReadPoly(){
    Polynomial P,Rear,t;
    int c,e,N;
    
    scanf("%d",&N);
    P=(Polynomial)malloc(sizeof(struct PolyNode));/*List head empty node*/
    P->link=NULL;
    Rear=P;
    while(N--){
        scanf("%d %d",&c,&e);
        Attach(c,e,&Rear);   /*Insert the current term at the end of the polynomial*/
    } 
    t=P;P=P->link;free(t); /*Delete temporarily generated header node*/
    return P;
}

Polynomial Add(Polynomial P1,Polynomial P2){
    Polynomial front,rear,temp;
    int sum;
    rear=(Polynomial)malloc(sizeof(struct PolyNode));
    front=rear;//front Used to record chain header nodes
    while(P1&&P2){

        switch(Compare(P1->expon,P2->expon)){
            case 1:
                Attach(P1->coef,P1->expon,&rear);
                P1=P1->link;
                break;
            case -1:
                Attach(P2->coef,P2->expon,&rear);
                P2=P2->link;
                break;
            case 0:
                sum=P1->coef+P2->coef;
                if (sum){
                    Attach(sum,P1->expon,&rear);
                }
                P1=P1->link;
                P2=P2->link;
                break;
            
        }
    }
    for(;P1;P1=P1->link) Attach(P1->coef,P1->expon,&rear);
    for(;P2;P2=P2->link) Attach(P2->coef,P2->expon,&rear);
    rear->link=NULL;
    temp=front;
    front=front->link;
    free(temp);
    return front;
} 

Polynomial Mult(Polynomial P1,Polynomial P2){
    Polynomial P,Rear,t1,t2,t;
    int c,e;
    if (!P1||!P2) return NULL;//Judge if P1 perhaps P2 There is one for NULL，The result is NULL; 
    
    t1=P1;t2=P2;
    P=(Polynomial)malloc(sizeof(struct PolyNode));
    P->link=NULL;
    Rear=P;
    while(t2){
        Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear);
        t2=t2->link;
    } 
    t1=t1->link;//t1 It's ready. Move back 
    while (t1){
        t2=P2;Rear=P;
        while(t2){
            e=t1->expon+t2->expon;
            c=t1->coef*t2->coef;
            while(Rear->link && Rear->link->expon>e)
            Rear=Rear->link;//When multiplied e When it is less than polynomial coefficient, Rear Pointer back 
            if(Rear->link && Rear->link->expon==e){
                if(Rear->link->coef+c)
                    Rear->link->coef+=c;//If the sum of coefficients of polynomials is not 0, the new coefficients are used for assignment 
                else{
                    t=Rear->link;
                    Rear->link=t->link;
                    free(t);//If the coefficient of the polynomial is 0, then Rear Pointer to next item, this node is released 
                }
            }
            else{
                t=(Polynomial)malloc(sizeof(struct PolyNode));
                t->coef=c;t->expon=e;
                t->link=Rear->link;
                Rear->link=t;Rear=Rear->link;//If the polynomial does not reach the end and there is no such item at present, then allocate memory space, create a new node, and insert the node into the linked list, Rear Pointer to new node t 
            } 
        t2=t2->link;     
        }
    t1=t1->link;    
    }
t2=P;P=P->link;free(t2);
return P;
}

void PrintPoly(Polynomial P){
    int flag=0;  //For auxiliary adjustment of output format
    
    if(!P) {printf("0 0\n");return;}
    
    while (P){
        if(!flag) flag=1;
        else printf(" ");
        printf("%d %d",P->coef,P->expon);
        P=P->link;
    }
    printf("\n");
} 

int main()
{
    Polynomial P1,P2,PP,PS;
    P1=ReadPoly();
    P2=ReadPoly();
    PP=Mult(P1,P2);
    PrintPoly(PP);
    PS=Add(P1,P2);
    PrintPoly(PS);
    
    return 0;
}