#P18563. Master of Modular Arithmetic

Master of Modular Arithmetic

Master of Modular Arithmetic

“拜托……我已经厌倦了那些数一些莫名其妙的东西、最后再对一个大质数取模的计数题。能不能来点不一样的?”

小青鱼热爱模运算,也精通处理模运算的技巧。为了检验你是否真正理解模运算的美妙,小青鱼给你一个由 nn 个正整数组成的序列 a1,a2,…,ana_1,a_2,\ldots,a_n。

你最多可以进行 2n+102n+10 次下列操作:

  1. 选择整数 xx,满足 1≤x≤1091\le x\le 10^9。
  2. 选择两个不同的下标 i,ji,j,满足 1≤i,j≤n1\le i,j\le n 且 i≠ji\ne j。
  3. 更新 ai←ai mod xa_i\leftarrow a_i\bmod x,同时更新 aj←aj⋅xa_j\leftarrow a_j\cdot x。

小青鱼希望你通过这些操作,把序列 aa 变成另一个序列 b1,b2,…,bnb_1,b_2,\ldots,b_n。判断是否可能,并在可能时输出方案。

这里 ai mod xa_i\bmod x 是除以正整数 xx 的非负余数。原题没有给中间整数设置上限;初始和目标数值的限制不表示操作过程受同一上界限制。

输入格式

输入含多组测试。第一行是整数 TT(T≥1T\ge1),表示测试组数。对每组测试:

  • 第一行一个整数 nn(1≤n≤5×1051\le n\le5\times10^5)。
  • 第二行 nn 个整数 a1,…,ana_1,\ldots,a_n(1≤ai≤1081\le a_i\le10^8),表示初始序列。
  • 第三行 nn 个整数 b1,…,bnb_1,\ldots,b_n(1≤bi≤1081\le b_i\le10^8),表示目标序列。

保证所有测试的 nn 之和不超过 5×1055\times10^5。

输出格式

对于每组测试:如果无法在 2n+102n+10 次操作内把 aa 变成 bb,输出一行 No。

否则,首先输出一行 Yes。下一行输出整数 mm(0≤m≤2n+100\le m\le2n+10),表示操作次数。接下来输出 mm 行,每行三个整数 i,j,xi,j,x,按执行顺序描述一次操作,满足题目中的全部要求。可以输出任意合法方案。

原样例

3
2
2 2
1 2
4
4 4 4 4
1 1 1 1
5
1 4 3 2 5
2 4 5 4 1
Yes
5
1 2 10
2 1 19
1 2 7
2 1 3
1 2 2
No
Yes
3
3 4 2
1 3 5
5 1 2

第一组给出的五次操作将 (2,2)(2,2) 依次变为 (2,20)(2,20)、(38,1)(38,1)、(3,7)(3,7)、(9,1)(9,1)、(1,2)(1,2)。第三组给出的方案依次得到 (1,4,1,4,5)(1,4,1,4,5)、(1,4,5,4,5)(1,4,5,4,5)、(2,4,5,4,1)(2,4,5,4,1)。