超大指数的稀疏乘法

题目描述

给定两个最高指数可能很大的稀疏多项式，计算它们的乘积。输入项可以无序、重复或系数为0。

输入格式

第一行输入A、B的项数n、m；接下来n行输入A的“系数 指数”，再接下来m行输入B的项。指数为非负整数。

数据范围与约定

• $1\le n,m\le 2\times 10^5$。
• 合并同类项并删除零系数后，两个多项式的非零项数分别记为 $n'$、$m'$，保证 $n'\times m'\le 2\times 10^6$。
• 输入系数的绝对值不超过 $10^9$，指数不超过 $10^{18}$。
• 输入保证任意两个指数之和不超过 $10^{18}$；合并同类项、系数相乘及同次项累加过程中的所有结果均在 signed 64-bit 整数范围内。

输出格式

第一行输出乘积非零项数t；随后按指数从高到低输出t行“系数 指数”。同指数项先合并，系数为0的项删除；零乘积只输出0。

样例

输入

2 2
3 1000000000
2 0
4 2
-1 0

输出

4
12 1000000002
-3 1000000000
8 2
-2 0