1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
| #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\n",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;
}
|
