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

typedef struct p { int c, e; struct p *n; } *P;

P new_p(int c, int e) {
    P t = malloc(sizeof(struct p));
    t->c = c; t->e = e; t->n = NULL; return t;
}

void insert_end(int c, int e, P *h) {
    P t = new_p(c, e);
    if (!*h) *h = t;
    else { P cur = *h; while (cur->n) cur = cur->n; cur->n = t; }
}

void attach(int c, int e, P *r) {
    (*r)->n = new_p(c, e); *r = (*r)->n;
}

P poly_add(P A, P B) {
    P r = new_p(0, 0), C = r;
    while (A && B) {
        int d = A->e - B->e;
        if (d < 0) { attach(B->c, B->e, &r); B = B->n; }
        else if (d > 0) { attach(A->c, A->e, &r); A = A->n; }
        else { int s = A->c + B->c; if (s) attach(s, A->e, &r); A = A->n; B = B->n; }
    }
    for (; A; A = A->n) attach(A->c, A->e, &r);
    for (; B; B = B->n) attach(B->c, B->e, &r);
    P t = C; C = C->n; free(t); return C;
}

void print_poly(P p) {
    if (!p) return;
    printf("%dx^%d", p->c, p->e);
    for (p = p->n; p; p = p->n) printf(" + %dx^%d", p->c, p->e);
    printf("\n");
}

int main() {
    P A = NULL, B = NULL;
    insert_end(3, 3, &A); insert_end(4, 2, &A); insert_end(1, 0, &A);
    printf("1st Polynomial: "); print_poly(A);
    insert_end(6, 4, &B); insert_end(5, 2, &B); insert_end(4, 1, &B);
    printf("2nd Polynomial: "); print_poly(B);
    P C = poly_add(A, B);
    printf("Added Polynomial: "); print_poly(C);
    return 0;
}