超大次数的稀疏多项式

题目描述

给定两个稀疏多项式A、B及运算符op。每个非零项用“系数 指数”表示，项可以无序且同一指数可以重复。计算A op B。

输入格式

第一行输入A的项数n、B的项数m和op；接下来n行输入A的项，再接下来m行输入B的项。op为+或-，指数均为非负整数。

输出格式

第一行输出结果的非零项数t；随后按指数从高到低输出t行，每行为系数和指数。同指数项先合并，系数为0的项不输出；零多项式只输出0。

样例

输入

3 3 -
3 1000000000
2 2
-5 0
1 1000000000
-2 2
7 1

输出

4
2 1000000000
4 2
-7 1
-5 0