This time, you are supposed to find A*B where A and B are two polynomials.

Input Specification:

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N1 a_N1 N2 a_N2 ... NK a_NK, where K is the number of nonzero terms in the polynomial, Ni and a_Ni (i=1, 2, ..., K) are the exponents and coefficients, respectively. It is given that 1 <= K <= 10, 0 <= NK < ... < N2 < N1 <=1000.

Output Specification:

For each test case you should output the product of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate up to 1 decimal place.

Sample Input

2 1 2.4 0 3.2

2 2 1.5 1 0.5

Sample Output

3 3 3.6 2 6.0 1 1.6

 #include <cstdio>

 #include <cstring>

 #include <string>

 #include <queue>

 #include <stack>

 #include <iostream>

 #include <cmath>

 using namespace std;

 #define exp 1e-9

 struct node{

     int e;

     double c;

     node *next;

 };

 int main(){

     //freopen("D:\\INPUT.txt","r",stdin);

     node *a,*b,*head;

     head=new node();

     head->next=NULL;

     int na;

     scanf("%d",&na);

     int i;

     a=new node[na];

     for(i=;i<na;i++){

         scanf("%d %lf",&a[i].e,&a[i].c);

     }

     int nb;

     scanf("%d",&nb);

     b=new node[nb];

     for(i=;i<nb;i++){

         scanf("%d %lf",&b[i].e,&b[i].c);

     }

     int j,num=;

     for(i=;i<na;i++){

         for(j=;j<nb;j++){

             int e=a[i].e+b[j].e;

             double c=a[i].c*b[j].c;

             node *q=head,*t=head->next;

             while(t){

                 if(t->e<e){//q->e>=e

                     break;

                 }

                 q=t;

                 t=q->next;

             }

             if(q!=head&&q->e==e){

                 q->c+=c;

             }

             else{

                 t=new node();

                 t->c=c;

                 t->e=e;

                 t->next=q->next;

                 q->next=t;

             }

         }

     }

     node *p;

     p=head->next;

     while(p){//系数可能为0！！  这里注意!!

         if(abs(p->c)>exp)

         num++;

         p=p->next;

     }

     p=head->next;

     printf("%d",num);

     while(p){

         if(abs(p->c)>exp)//系数可能为0！！

         printf(" %d %.1lf",p->e,p->c);

         head->next=p->next;

         delete p;

         p=head->next;

     }

     printf("\n");

     delete []a;

     delete []b;

     delete head;

     return ;

 }