两份指数名单合并

题目描述

给定两个正整数的标准质因数指数表，直接计算两数乘积的指数表：相同质因数的指数相加，只在一份表中出现的质因数保持原指数。不得先还原整数。

输入格式

先输入 k1 及 k1 行 p、e，再输入 k2 及 k2 行 p、e。每份表内部 p 严格递增；1≤k1,k2≤30、2≤p≤10^9、1≤e≤10^9。

输出格式

逐行输出合并后的 p、e，每个质因数一行，并按 p 严格递增。

样例

输入

1
2 1
1
3 1

输出

2 1
3 1