def gcd(m, n)
	if m < n 
		gcd(n, m)
	elsif n == 0
		m
	else
		gcd(n, m % n)
	end 
end

def lcm(m, n)
	m * n / gcd(m, n)
end

class Array
    def ary_gcd
        inject{|l, x| gcd(l, x)}
    end
    def ary_lcm
        inject{|l, x| lcm(l, x)}
    end
end

class Poly < Hash
    def self.var
        x = self.new(0)
        x[1] = 1
        x
    end

    def degree
        self.keys.max || 0
    end

    def self.num(n)
        d = self.new(0)
        d[0] = n
        d
    end

    def normalize!
        each_key do |k|
            delete(k) if self[k] == 0
        end
        self
    end

    def +(other)
        sum = self.class.num(0)
        self.each {|k, c| sum[k] += c}
        other.each {|k, c| sum[k] += c}
        sum.normalize!
    end

    def -(other)
        diff = self.class.num(0)
        self.each {|k, c| diff[k] += c}
        other.each {|k, c| diff[k] -= c}
        diff.normalize!
    end

    def -@
        m = self * self.class.num(-1)
        m.normalize!
    end

    def *(other)
        prod = self.class.num(0)
        self.each do |k1, c1| 
            other.each do |k2, c2|
                prod[k1 + k2] += c1 * c2
            end
        end
        prod.normalize!
    end

    def **(k)
        return Poly.num(1) if k == 0
        return self if k == 1
        self * self ** (k - 1)
    end

    def zero?
        self.empty? || (degree == 0 && self[0] == 0)
    end

    def to_integral
        l = values.map {|x| x.kind_of?(Rational) ? x.denominator : 1}.ary_lcm
        v = self * Poly.num(l)
        g = v.values.map(&:to_i).map(&:abs).ary_gcd
        v.each_key {|k| v[k] = (v[k] / g).to_i}
        if v[v.degree] < 0
            v.each_key {|k| v[k] *= -1} 
        end
        v
    end

    def to_s
        x = to_integral
        a = x.keys.sort.reverse.map do |k|
            if k == 0
                x[k]
            else
                "#{x[k] == 1 ? '' : (x[k] == -1 ? ?- : x[k])}x#{k==1 ? '' : ?^ + k.to_s}"
            end
        end
        a.join(?+).gsub("+-", ?-)
    end

end

def get_exp(s, i)
    if s[i] == ?-
        t, j = get_term(s, i+1)
        return nil unless t

        j += 1 if s[j] == ?+
        e, k = get_exp(s, j)
        if e
            return [-t + e, k] if e
        else
            return [-t, j]
        end
    end

    t, j = get_term(s, i)
    return nil unless t

    j += 1 if s[j] == ?+
    e, k = get_exp(s, j)
    if e
        return [t + e, k] if e
    else
        return [t, j]
    end
end

def get_term(s, i)
    f, j = get_factor(s, i)
    return nil unless f

    t, k = get_term(s, j)
    if t
        return [f * t, k]
    else
        return [f, j]
    end
end

def get_factor(s, i)
    pr, j = get_primary(s, i)
    return nil unless pr
    if s[j] == ?^
        d, k = get_number(s, j+1)
        return nil unless d
        return [pr**d, k]
    else
        return [pr, j] 
    end
end

def get_primary(s, i)
    return [Poly::var, i+1] if s[i] == ?x
    v, j = get_number(s, i)
    return [Poly::num(v), j] if v
    return nil unless s[i] == ?(
    e, j = get_exp(s, i+1)
    return nil unless e && s[j] == ?)
    return [e, j+1]
end

def get_number(s, i)
    return nil unless s[i] =~ /\d/
    j = i
    j += 1 while s[j] =~ /\d/
    return [s[i..j-1].to_i, j]
end

require 'rational'
def poly_gcd(e1, e2)
    return poly_gcd(e2, e1) if e1.degree < e2.degree
    return e1 if e2.zero?

    until e1.zero? || e1.degree < e2.degree 
        r = Rational(e1[e1.degree], e2[e2.degree])
        e1 -= e2 * Poly::num(r) * Poly::var ** (e1.degree - e2.degree)
    end

    poly_gcd(e2, e1)
end

loop do
    s = gets.chomp
    break if s == ?.
    e1, _ = get_exp(s, 0)
    s = gets.chomp
    e2, _ = get_exp(s, 0)
    puts poly_gcd(e1, e2)
end

Measured memory_bytes: 9084