NOI2018 屠龙骑士
每次面对巨龙时，机器人会选择当前拥有的，攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑，则选择攻击力最低的一把剑作为武器。
也就是 这个剑的选择已经给定了。
找到选的剑可以通过手写平衡树，但是这是D2T1 手写平衡树太毒瘤了 我们有内置红黑树的set/multiset！支持upper_bound和lower_bound。
显然攻击力可能会重复，所以不能用set。
那就直接multiset上！
选好了显然要计算还需要多少刀才能砍死巨龙。
首先显然要把巨龙砍到再砍一刀生命就为负数，这些刀必须砍。
然后剩下的，设攻击力为s，恢复能力为p，生命为a。
在$\gcd(s,p)|a$的前提下（否则就打不死了），可以把$a,p,s$全部除以$\gcd(a,p)$，这样就方便计算了。下面的$a,p,s$都是除后的。
首先可以exgcd解出最少要砍几刀。
这个值需要$\bmod p$，如果=0并且$a\not =0$，那还最少砍的次数就应该是p。如果a=0，还最少要砍的次数就应该是0。
假设最少要砍k刀。
之后显然多砍p刀是没有影响的。
就得到了一个方程：
$$x\equiv k\pmod p$$且$x\ge k$。
由于这些方程不互质，就不能直接CRT而是要用exCRT。
他们的写法都好玄学我完全看不懂
把每个方程的p分解质因数，拆成$O(\log p)$个方程。
然后把模数的底数相同的合并，就合并成$O(\log \mathrm{lcm})$个方程了。
但是分解是$O(n\sqrt{p})$的好慢啊...
可以先计算出lcm并对lcm分解质因数 显然不需要Pollard Rho可以直接根号分解，然后底数就只有可能是这$O(\log \textrm{lcm})$个质因数。
分解的时候就只需要考虑这些质因数了 。
exCRT出答案以后，如果不满足$\ge k$的限制，，， 由于答案是$\bmod \textrm{lcm}$意义下的，设算出来答案为S，$\max\{k\}=M$，答案只需要+$\lceil\frac{M-S}{\textrm{lcm}}\rceil \textrm{lcm}$就好。
显然$\lceil\frac{M-S}{\textrm{lcm}}\rceil=\lfloor\frac{M-S}{\textrm{lcm}}\rfloor+[(M-S)\bmod \text{lcm} \not=0]$。
时间复杂度$O(n\log \textrm{lcm} +\sqrt{\textrm{lcm}})$。
/*
Author: CNYALI_LK
LANG: C++
PROG: dragon.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
ll s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
multiset<ll> t;
multiset<ll>::iterator it;
ll a[102424],p[102424],b[102424],ys[102424],atl[102424],_ans;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void exgcd(ll a,ll b,ll &x,ll &y){
if(!b){x=1;y=0;return;}
exgcd(b,a%b,y,x);
y-=(a/b)*x;
}
ll Calc(ll a,ll b,ll &c,ll &d,ll &e){
e=b/a;
b%=a;
ll h=gcd(a,c),x,y;
if(b%h)return 1;
a/=h;b/=h;c/=h;
exgcd(a,c,x,y);
if(b)
x=((x%c+c)%c*b+c-1)%c+1;
else
x=0;
e+=x;
d=e%c;
chkmax(_ans,e);
return 0;
}
ll st,ax[102424],px[102424];
ll mul(ll a,ll b,ll p){
ll c=0;
for(;b;b>>=1,a=(a+a)%p)if(b&1)c=(c+a)%p;
return c;
}
ll CRT(ll n){
ll s=1,sum=0,x,y;
for(ll i=1;i<=n;++i)s*=px[i];
for(ll i=1;i<=n;++i){
exgcd(s/px[i],px[i],x,y);
x=(x%px[i]+px[i])%px[i];
sum=(sum+mul(mul(x,(s/px[i]),s),ax[i],s))%s;
}
return sum;
}
void calc(ll n){
ll s=1,h,pxy,xl,stdc;
for(ll i=1;i<=n;++i)s=s/gcd(s,p[i])*p[i];
stdc=s;
st=0;
for(ll i=2;i*i<=s;++i)if(!(s%i)){
++st;
px[st]=1;
ax[st]=0;
while(!(s%i)){
s/=i;
px[st]*=i;
}
xl=1;
for(ll j=1;j<=n;++j)if(!(p[j]%i)){
pxy=1;
while(!(p[j]%i)){
pxy*=i;
p[j]/=i;
}
if(pxy>xl){
if(ys[j]%xl!=ax[st]){printf("-1\n");return;}
else {xl=pxy;ax[st]=ys[j]%pxy;}
}
else{
if(ys[j]%pxy!=ax[st]%pxy){printf("-1\n");return;}
}
}
}
if(s>1){
++st;
px[st]=s;
ax[st]=0;
xl=1;
for(ll j=1;j<=n;++j)if(!(p[j]%s)){
pxy=1;
while(!(p[j]%s)){
pxy*=s;
p[j]/=s;
}
if(pxy>xl){
if(ys[j]%xl!=ax[st]){printf("-1\n");return;}
else {xl=pxy;ax[st]=ys[j]%pxy;}
}
else{
if(ys[j]%pxy!=ax[st]%pxy){printf("-1\n");return;}
}
}
}
ll ans=CRT(st),ax;
if(ans<_ans){
ax=((_ans-ans)/stdc)+!!((_ans-ans)%stdc);
ans=ans+ax*stdc;
}
printf("%lld\n",ans);
}
int main(){
freopen("dragon.in","r",stdin);
freopen("dragon.out","w",stdout);
ll T,n,m,s;
T=read();
for(;T;--T){
n=read();m=read();
for(ll i=1;i<=n;++i)a[i]=read();
for(ll i=1;i<=n;++i)p[i]=read();
for(ll i=1;i<=n;++i)b[i]=read();
t.erase(t.begin(),t.end());
for(ll i=1;i<=m;++i)t.insert(read());
ll ok=1;
_ans=0;
for(ll i=1;i<=n;++i){
it=t.upper_bound(a[i]);
if(it==t.begin())s=*it;
else s=*(--it);
t.erase(it);
if(Calc(s,a[i],p[i],ys[i],atl[i])){printf("-1\n");ok=0;break;};
t.insert(b[i]);
}
if(ok)calc(n);
}
return 0;
}