Description：

给一个方程组： $$ \begin{cases} c_1x&\equiv&m_1&\pmod {p_1}\\ c_2x&\equiv&m_2&\pmod {p_2}\\ &&\vdots\\ c_nx&\equiv&m_n&\pmod {p_n}\end{cases} $$

$1\leqslant n\leqslant 10^5$

Solution：

扩展中国剩余定理裸题：

首先我们应该先把 $c_i$ 除到右边去，但是如果 $\gcd(c_i,p_i)\ne 1$ 那么就没有逆元，但是考虑这个式子的本质是： $$ c_ix+kp_i=m $$ 那么我们把 $a_i,p_i,m$ 都除掉 $\gcd(c_i,p_i,m)$ 还是成立的，这个时候如果 $\gcd(c_i,p_i)\ne 1$ 并且，那么肯定无解，因为 $m\not|\gcd(c_i,p_i)$ 。

于是我们现在成功把方程组化成了： $$ \begin{cases} x&\equiv&m_1&\pmod {p_1}\\ x&\equiv&m_2&\pmod {p_2}\\ &&\vdots\\ x&\equiv&m_n&\pmod {p_n} \end{cases} $$ 于是这个就是裸的 $exCRT$ 了，再推一遍式子： $$ x=m_1+p_1k_1=m_2+p_2k_2\Rightarrow p_1k_1-p_2k_2=m_2-m_1 $$ $exgcd$ 解出一组解，然后把方程合并成 $x\equiv m'\pmod{\text{lcm}(p_1,p_2)}$ 的形式即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

inline ll rd()

{

	register ll res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXN 100010

ll a[MAXN],p[MAXN],v[MAXN];

multiset<ll> s;

ll c[MAXN];

ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b,a % b));}

ll x[MAXN];

ll mul(ll a,ll b,ll p)

{

	ll res = 0;

	for(;b > 0;b = b >> 1,a = (a + a) % p)if(b & 1)res = (res + a) % p;

	return res;

}

ll exgcd(ll a,ll b,ll &x,ll &y)

{

	if(b == 0){x = 1;y = 0;return a;}

	ll t = exgcd(b,a % b,y,x);

	y -= x * (a / b);

	return t;

}

ll calcinv(ll k,ll p)

{

	ll x,y;

	exgcd(k,p,x,y);

	x = (x % p + p) % p;

	return x;

}

void work()

{

	scanf("%d%d",&n,&m);

	s.clear();

	for(int i = 1;i <= n;++i)a[i] = rd();

	for(int i = 1;i <= n;++i)p[i] = rd();

	int sum = 0;

	for(int i = 1;i <= n;++i)sum += (p[i] == 1);

	for(int i = 1;i <= n;++i)v[i] = rd();

	for(int i = 1;i <= m;++i)s.insert(rd());

	for(int i = 1;i <= n;++i)

	{

		multiset<ll>::iterator it = s.begin();

		if(*it < a[i])it = --s.upper_bound(a[i]);

		c[i] = *it;s.erase(it);

		s.insert(v[i]);

	}

	if(sum == n)

	{

		ll ans = 0;

		for(int i = 1;i <= n;++i)ans = max(ans,(ll)ceil(1.0 * a[i] / c[i]));

		cout << ans << endl;

		return;

	}

	for(int i = 1;i <= n;++i)

	{

		ll g = gcd(c[i],gcd(a[i],p[i]));

		c[i] /= g;a[i] /= g;p[i] /= g;

		if(gcd(c[i],p[i]) != 1)

		{

			puts("-1");

			return;

		}

		ll inv = calcinv(c[i],p[i]);

		x[i] = mul(a[i],inv,p[i]);

	}

	ll X = x[1],P = p[1];

	for(int i = 2;i <= n;++i)

	{

		if(x[i] < X)swap(x[i],X),swap(p[i],P);

		ll xx,yy;

		ll g = exgcd(P,p[i],xx,yy);

		if((x[i] - X) % g != 0)

		{

			puts("-1");

			return;

		}

		ll newP = P / gcd(P,p[i]) * p[i];

		ll t = (x[i] - X) / g;

		xx = (xx + newP) % newP;

		xx = mul(xx,t,newP);

		ll res = (X + mul(P,xx,newP)) % newP;

		X = res;P = newP;

	}

	printf("%lld\n",X);

	return;

}

int main()

{

	int testcases = rd();

	while(testcases--)work();

	return 0;

}