UOJ Logo PP Online Judge

PPOJ

#111. 数据结构实验1-2: 一元稀疏多项式加法

统计

描述

计算两个多项式的和,例如:多项式 $4x^5-5x^3+6x^4+2x$ 与多项式 $6x^6+3x^4+2x^3+x^2+5$ 的和为 $6x^6+4x^5+9x^4-3x^3+x^2+2x+5$,输入的两个多项式不一定按指数排序,但输出的多项式需要按指数从高到低排序。

输入

输入数据第 1 行为正整数 $n$ 表示第一个多项式的项数,后面紧跟 $n$ 行,每行两个整数, 分别表示该项的系数和指数,接下来一行是一个整数 $m$ 表示第二个多项式的项数 $m$,后面 紧跟 $m$ 行,每行两个整数,分别表示该项的系数和指数。

输出

以多项式的形式在一行输出求和结果,指数前加符号"^",系数为负数时输出减号,系数为 $1$ 时不输出系数。

数据范围

$n, m <= 1000$, 保证计算结果在 int 范围内。
注意多项式的系数可能会有0,如果这个多项式是0多项式就什么都不输出了

样例一

样例输入

4 
4 5 
-5 3 
6 4 
2 1 
5
6 6 
3 4 
2 3 
1 2
5 0

样例输出

6x^6+4x^5+9x^4-3x^3+x^2+2x+5

来源

数据结构上机