The Errant Physicist

The well-known physicist Alfred E Neuman is working on problems that involve multiplying polynomials of x and y. For example, he may need to calculate

getting the answer

Unfortunately, such problems are so trivial that the great man's mind keeps drifting off the job, and he gets the wrong answers. As a consequence, several nuclear warheads that he has designed have detonated prematurely, wiping out five major cities and a couple of rain forests.

You are to write a program to perform such multiplications and save the world.

Input

The file of input data will contain pairs of lines, with each line containing no more than 80 characters. The final line of the input file contains a # as its first character. Each input line contains a polynomial written without spaces and without any explicit exponentiation operator. Exponents are positive non-zero unsigned integers. Coefficients are also integers, but may be negative. Both exponents and coefficients are less than or equal to 100 in magnitude. Each term contains at most one factor in x and one in y.

Output

Your program must multiply each pair of polynomials in the input, and print each product on a pair of lines, the first line containing all the exponents, suitably positioned with respect to the rest of the information, which is in the line below.

The following rules control the output format:

1. Terms in the output line must be sorted in decreasing order of powers of x and, for a given power of x, in increasing order of powers of y.
2. Like terms must be combined into a single term. For example, 40x²y³ - 38x²y³ is replaced by 2x²y³.
3. Terms with a zero coefficient must not be displayed.
4. Coefficients of 1 are omitted, except for the case of a constant term of 1.
5. Exponents of 1 are omitted.
6. Factors of x⁰ and y⁰ are omitted.
7. Binary pluses and minuses (that is the pluses and minuses connecting terms in the output) have a single blank column both before and after.
8. If the coefficient of the first term is negative, it is preceded by a unary minus in the first column, with no intervening blank column. Otherwise, the coefficient itself begins in the first output column.
9. The output can be assumed to fit into a single line of at most 80 characters in length.
10. There should be no blank lines printed between each pair of output lines.
11. The pair of lines that contain a product should be the same length--trailing blanks should appear after the last non-blank character of the shorter line to achieve this.

Sample Input

-yx8+9x3-1+y
x5y+1+x3
1
1
#

Sample Output

  13 2    11      8      6    5     5 2     3    3
-x  y  - x  y + 8x y + 9x  - x y + x y  + 8x  + x y - 1 + y 

1

#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
using namespace std;
struct F {//factor
    int k, x, y;
    F(int a, int b, int c):
        k(a), x(b), y(c) {}
    bool operator<(const F &a) const {
        if(x != a.x)
            return x > a.x;
        return y < a.y;
    }
};
vector<F> parsePoly(char s[]) {
    vector<F> ret;
    int i, len = strlen(s);
    for(i = 0; i < len;) {
        int sign = 1, k, x, y;
        if(s[i] == '-')
            sign = -1, i++;
        if(s[i] == '+')
            sign = 1, i++;
        if(s[i] >= '0' && s[i] <= '9') {
            k = 0;
            while(s[i] >= '0' && s[i] <= '9')
                k = k*10 + s[i]-'0', i++;
        } else
            k = 1;
        x = 0, y = 0;
        if(s[i] == 'x') {
            i++;
            if(s[i] >= '0' && s[i] <= '9') {
                x = 0;
                while(s[i] >= '0' && s[i] <= '9')
                    x = x*10 + s[i]-'0', i++;
            } else
                x = 1;
        }
        if(s[i] == 'y') {
            i++;
            if(s[i] >= '0' && s[i] <= '9') {
                y = 0;
                while(s[i] >= '0' && s[i] <= '9')
                    y = y*10 + s[i]-'0', i++;
            } else
                y = 1;
        }
        if(s[i] == 'x') {
            i++;
            if(s[i] >= '0' && s[i] <= '9') {
                x = 0;
                while(s[i] >= '0' && s[i] <= '9')
                    x = x*10 + s[i]-'0', i++;
            } else
                x = 1;
        }
        ret.push_back(F(k*sign, x, y));
    }
    return ret;
}
int main() {
    char s[105];
    while(scanf("%s", s) == 1) {
        if(s[0] == '#')
            break;
        vector<F> A, B;
        A = parsePoly(s);
        scanf("%s", s);
        B = parsePoly(s);
        map<F, int> ret;
        for(vector<F>::iterator it = A.begin();
            it != A.end(); it++) {
            for(vector<F>::iterator jt = B.begin();
                jt != B.end(); jt++) {
                int x = it->x + jt->x, y = it->y + jt->y;
                F IDX(0, x, y);
                ret[IDX] += it->k * jt->k;
            }
        }
        char out[2][1005] = {};
        int oidx1 = 0, oidx2 = 0;
        int first = 0;
        for(map<F, int>::iterator it = ret.begin();
            it != ret.end(); it++) {
            if(it->second == 0) continue;
            if(first && it->second > 0) {
                out[1][oidx2++] = ' ';
                out[1][oidx2++] = '+';
                out[1][oidx2++] = ' ';
            }
            if(it->second < 0) {
                if(first) {
                    out[1][oidx2++] = ' ';
                    out[1][oidx2++] = '-';
                    out[1][oidx2++] = ' ';
                } else {
                    out[1][oidx2++] = '-';
                }
                it->second = -(it->second);
            }
            first = 1;
            if(it->second != 1 || (it->first.x == 0 && it->first.y == 0)) {
                sprintf(out[1]+oidx2, "%d", it->second);
                while(out[1][oidx2])    oidx2++;
            }
            if(it->first.x) {
                out[1][oidx2++] = 'x';
                if(it->first.x > 1) {
                    while(oidx1 < oidx2)
                        out[0][oidx1++] = ' ';
                    sprintf(out[0]+oidx1, "%d", it->first.x);
                    while(out[0][oidx1])
                        oidx1++;
                    while(oidx2 < oidx1)
                        out[1][oidx2++] = ' ';
                }
            }
            if(it->first.y) {
                out[1][oidx2++] = 'y';
                if(it->first.y > 1) {
                    while(oidx1 < oidx2)
                        out[0][oidx1++] = ' ';
                    sprintf(out[0]+oidx1, "%d", it->first.y);
                    while(out[0][oidx1])
                        oidx1++;
                    while(oidx2 < oidx1)
                        out[1][oidx2++] = ' ';
                }
            }
            while(oidx1 < oidx2)
                out[0][oidx1++] = ' ';
            while(oidx2 < oidx1)
                out[1][oidx2++] = ' ';
        }
        puts(out[0]);
        puts(out[1]);
    }
    return 0;
}
/*
-yx8+9x3-1+y
x5y+1+x3
*/