Using your chosen programming language, write a program that adds and subtracts polynomials. Each polynomial should be represented as a linked-list. The first node in the list represents the first term in the polynomial, the second node represents the second term, and so forth.

Each node contains three fields. The first field is the terms coefficient. The second field is the terms power, and the third field is a pointer to the next term. For example, consider the polynomial shown below. The first term in the first polynomial has a coefficient of 5 and an exponent of 4, which is interpreted as 5x4.

P1: 5x4+ 6x3+7

P2: 2x3+ 7x2+3x

Result: 5x4+ 8x3- 7x2+3x + 7

The rule for the addition of polynomials are as follows:

1. If the powers are equal, the coefficients are algebraically added.

2. If the powers are unequal, the term with the higher power is inserted in the new polynomial.

3. If the exponent is zero, it represents x0, which is 1. The value of the term is therefore the value of the coefficients.

4. If the result of adding the coefficients results in 0, the term is dropped (zero times anything is 0).

A polynomial is represented by a series of lines, each of which has two integers. The first integer represents the coefficient; the second integer represents the exponent. Thus, the polynomial P1 would have (5 4), (6 3), and (7 0).

To add two polynomials, the program reads the coefficients and exponents for each polynomial and places them into a linked list. The input is read from a file or entered from the keyboard. After the polynomial has been stored, they are added and the results are placed in a third linked list.

The polynomials are added using an operational merge process. An operational merge combines the two lists while performing one or more operations - in our case, addition. To add, we take one term from each of the polynomials and compare the exponents. If the two exponents are equal, then the coefficients are added to create a new coefficient. If the new coefficient is 0, then the entire term is dropped; if it is not 0, it is appended to the linked list for the resulting polynomial. If one of the exponents is larger than than the other, the corresponding term is immediately placed into the new linked list, and the term with the smaller exponent is held to be compared with the next term from the other list. If one list ends before the other, the rest of the longer list is simply appended to the list for the new polynomial.

Print the two input polynomials and their sum by traversing the linked lists and displaying them as a set of numbers. Be sure to label each polynomial.

Sample Input

7 9 2 6 3 5 4 4 2 3 6 2 6 0

-7 9 2 8 -5 7 2 4 2 3 9 2 -7 1

Sample Output

P1: 7x^9 + 2x^6 + 3x^5 + 4x^4 + 2x^3 + 6x^2 + 6

P2: -7x^9 + 2x^8 + -5x^7 + 2x^4 + 2x^3 + 9x^2 + -7x

Result: 2x^8 + -5x^7 + 2x^6 + 3x^5 + 6x^4 + 4x^3 + 15x^2 + -7x + 6

Include explanation of the analysis of the algorithm efficiency of the program.