28929번 - Многочлены 스페셜 저지다국어

문제

Снежок нашел листок из старого учебника по математике. На нем перечислены $t$ многочленов от двух переменных.

Теперь Снежок хочет их упростить. Помогите ему.

Во входном файле многочлены записаны в следующем формате:

• Многочлен не содержит пробелов и состоит только из арабских цифр и символов <<n>>, <<m>>, <<+>>, <<->>, <<*>>, <<^>>.
• Многочлен состоит из нескольких слагаемых.
• Если слагаемое входит со знаком минус, то перед ним пишется <<->>.
• Если слагаемое входит со знаком плюс и это не первое слагаемое, то перед ним пишется <<+>>.
• Каждое слагаемое можно представить в виде $a\cdot n^{b}\cdot m^{c},ドル где $a,ドル $b$ и $c$ --- целые неотрицательные числа (если не учитывать знак перед слагаемым), без ведущих нулей, не превышающие 10ドル^5$.
• Слагаемое записывается в следующем формате:
  • Слагаемое является произведением чисел и степеней $n$ и $m$.
  • Назовем числом последовательность подряд идущих цифр, слева и справа от которой стоят не цифры.
  • Перед каждым символом <<^>> находится переменная, то есть символ <<n>> или символ <<m>>.
  • После каждого символа <<^>> находится число.
  • Таким образом, знак <<^>> обозначает, что переменная, стоящая перед ним, возводится в степень числа, стоящего после него. Назовем это множителем.
  • Если после символов <<n>> или <<m>> нет символа <<^ >>, то считается, что эта переменная в этом месте стоит в степени 1ドル$. Назовем каждую такую переменную множителем.
  • Все числа, которые не являются степенями (то есть, те, перед которыми не стоят символы <<^>>), назовем множителями.
  • По обе стороны от каждого символа <<*>> находятся множители.
  • Слагаемое это произведение всех его множителей.
  • Обращаем ваше внимание, что некоторые соседние множители могут не разделяться символом <<*>>.

Для упрощенного многочлена должно выполняться следующее:

• Он записывается в таком же формате, как и исходный.
• Если многочлен тождественно равен нулю, нужно вывести <<0>>.
• Если слагаемое представимо в виде $a \cdot n^b \cdot m^c,ドル то такое слагаемое должно быть записано как <<an^ bm^ c>>, где на место <<a>>, <<b>> и <<c>> подставлены соответствующие числа.
• Для каждой пары $a$ и $b$ существует не более одного слагаемого, представимого в виде $k\cdot n^a\cdot m^b$.
• Если $n^a\cdot m^b$ входит в многочлен с коэффициентом 0, такое слагаемое писать не надо.
• Если $n^a\cdot m^b$ входит в многочлен с коэффициентом, по модулю равным 1, в таком слагаемом не нужно писать коэффициент.
• В слагаемом вида $a\cdot n^0 \cdot m^c,ドル переменную <<n>> писать не надо.
• В слагаемом вида $a\cdot n^1 \cdot m^c,ドル после переменной <<n>> не нужно писать степень.
• Для переменной <<m>> тоже выполняются предыдущие два пункта.
• Слагаемые в многочлене могут идти в любом порядке.

입력

В первой строке задано целое число $t$ --- количество многочленов (1ドル \le t \le 100$). В следующих $t$ строках заданы многочлены. Гарантируется, что все числа в них не превосходят 10ドル^5$.

Длины всех строк не превосходят 100ドル$.

출력

Для каждого многочлена выведите его в упрощенном виде.

Гарантируется, что в упрощенном многочлене все числа не превосходят 10ドル^9$.

제한

노트

Пояснение к примеру:

$-n^{2}*m^{1}+n*nm3+mn-n+m-n*m = m-n+2n^{2}m$

$n*n*m^{0}m^{2}*5-m*2n = -2nm+5n^{2}m^{2}$

$-100n*m+23+0n^{3} = 23-100nm$

$n-n = 0$

100000ドル*100000*100000*n^{3}*n^{4}*0+nm^{2} = nm^{2}$

Обращаем ваше внимание, что хотя в процессе вычисления значения коэффициента в первом слагаемом последнего многочлена оно и становится больше 10ドル^5,ドル но в итоге это слагаемое равно 0ドル\cdot n^3\cdot n^4,ドル значит для него ограничение на величину коэффициента тоже выполняется.