幂的新身份证

题目描述

给定正整数 N 的标准质因数指数表和正整数 m，求 N^m 的标准表。整体乘方会把每个质因数指数乘以 m。

输入格式

先输入 k 及 k 行 p、e，最后输入 m。满足 1≤k≤100、1≤m≤10^9，新指数不超过64位上限。

输出格式

第一行输出 k；随后按原有质数递增顺序输出 p 和新指数 e×m。

样例

输入

1
2 1
2

输出

1
2 2