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;
}
};