屠龙勇士
很久很久以前，巨龙突然出现，带来了灾难带走公主又消失不见。王国十分危险，世间谁最勇敢，一位英雄出现……
学习于该大佬博客
那么你就是这位英雄，不过不同的是，你面对的是一群巨龙，虽然巨龙都不会攻击；你每次使用的剑一打就爆，虽然每打死一条巨龙的奖励是一把新的剑；巨龙不会因为生命值降为负数而死亡，虽然巨龙会憨憨地回血然后把自己奶死；最重要的是你完成游戏不会获得公主的爱，只会获得参加ION8012的报名机会。你一听到最后一条彻底就失去了兴致，于是写了一个机器人帮你完成任务XD
简单来说，就是求解同余方程组：
[k_ixequiv a_i(mod p_i)
]
其中i为巨龙个数1-n。
然鹅，你会惊讶地发现，如果用扩展中国剩余定理的话，我们只能求解出左项x的系数为1的式子。这对于身经百战的你当然不是问题，一下子就想到了将(k_i)化掉的好方法：
原式可化为：
[k_ix + p_iyequiv a_i
]
用设(g=gcd(k_i,p_i))，那么用扩展欧几里得求出(x')（一组解），原式可化为
[xequiv frac{a_i}{g}x′(modfrac {p_i}{g})
]
然后我们就化成了系数为1的情况。我们就可以解辣♪(∇*)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<set>
#define int long long
using namespace std;
inline int read()
{
int x=0,w=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return w?-x:x;
}
namespace star
{
const int maxn=1e5+100;
multiset<int >sword;
multiset<int >::iterator it;
int a[maxn],p[maxn],sw[maxn],n,m;
inline void init(){
memset(a,0,sizeof a);
memset(p,0,sizeof p);
memset(sw,0,sizeof sw);
sword.clear();
n=read(),m=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)p[i]=read();
for(int i=1;i<=n;i++)sw[i]=read();
while(m--)sword.insert(read());
}
void exgcd(int a,int b,int& d,int &x,int &y){
if(!b)d=a,x=1,y=0;
else exgcd(b,a%b,d,y,x),y-=(a/b)*x;
}
inline int mul(int b,int k,int m){
int a=0;
for(;k;k>>=1,b=(b<<1)%m)
if(k&1)a=(a+b)%m;
return a;
}//龟速乘，防止溢出
inline int getsword(int i){
it=sword.upper_bound(a[i]);
if(it!=sword.begin())--it;
int zp=*it;
sword.erase(it);sword.insert(sw[i]);
return zp;
}
inline void excrt(){
int X,Y,k;
int m=1,ans=0,mx=0,G;
for(int i=1;i<=n;i++){
k=getsword(i);
mx=max(mx,(a[i]-1)/k+1);
k%=p[i];a[i]%=p[i];
if(!k&&a[i]){puts("-1");return;}//无解
if(!k&&!a[i])continue;//说明此同余方程没有作用，必须跳过
exgcd(k,p[i],G,X,Y);
if(a[i]%G){puts("-1");return;}
p[i]/=G;
a[i]=mul(a[i]/G,(X%p[i]+p[i])%p[i],p[i]);
exgcd(m,p[i],G,X,Y);
if((a[i]-ans)%G){puts("-1");return;}
m=m/G*p[i];
ans=(ans+mul(mul(m/p[i],((a[i]-ans)%m+m)%m,m),(X%m+m)%m,m))%m;
}
printf("%lld
",ans>=mx?ans:ans+m*((mx-ans-1)/m+1));
}
inline void work(){
init();
excrt();
}
}
signed main()
{
int t=read();
while(t--)star::work();
return 0;
}