class Polynomial {
private:
    Node* head;

public:
    Polynomial() : head(nullptr) {}

    // Insert a new term in descending order of powers
    void insertTerm(int coeff, int power) {
        Node* newNode = new Node(coeff, power);

        // if list is empty or new term has highest power
        if (!head || head->power < power) {
            newNode->next = head;
            head = newNode;
            return;
        }

        Node* temp = head;
        Node* prev = nullptr;

        while (temp && temp->power > power) {
            prev = temp;
            temp = temp->next;
        }

        // if same power → combine coefficients
        if (temp && temp->power == power) {
            temp->coeff += coeff;
            delete newNode;
        } else {
            newNode->next = temp;
            if (prev) prev->next = newNode;
        }
    }

    // Display the polynomial
    void display() const {
        Node* temp = head;
        while (temp) {
            cout << temp->coeff << "x^" << temp->power;
            if (temp->next && temp->next->coeff >= 0) cout << " + ";
            else if (temp->next) cout << " ";
            temp = temp->next;
        }
        cout << endl;
    }

    // Add two polynomials
    static Polynomial add(const Polynomial& p1, const Polynomial& p2) {
        Polynomial result;
        Node* a = p1.head;
        Node* b = p2.head;

        while (a || b) {
            if (a && (!b || a->power > b->power)) {
                result.insertTerm(a->coeff, a->power);
                a = a->next;
            } else if (b && (!a || b->power > a->power)) {
                result.insertTerm(b->coeff, b->power);
                b = b->next;
            } else {
                // same power
                result.insertTerm(a->coeff + b->coeff, a->power);
                a = a->next;
                b = b->next;
            }
        }

        return result;
    }
};