学生零太强大了。
考虑到题目保证了 \(p, q \le 3 \times 10^9\)。记值域 \(V = 3 \times 10^9\)。
则我们声称，取一个大质数 \(P > V^2\)，然后求出 \(\left(\prod \limits_{i = 1}^n a_i\right)\left(\prod \limits_{i = 1}^m b_i\right)^{-1} \equiv x \pmod {P}\)。则如果找到了 \(x \cdot y^{-1} \equiv x \pmod {P}\)，则我们求得的 \(x, y\) 就是最终的答案。
由定义 \(\frac{p}{q} \equiv \frac{x}{y} \pmod {P}\)。
那么 \(py \equiv qx \pmod {P}\)，即 \(py - qx = kP, k \isin \N\)。
显然 \(py - qx < V^2, kP > V^2\)，因此 \(py - qx = 0\)，即 \(\frac{p}{q} = \frac{x}{y}\)。
现在要解同余方程 \(\frac{p}{q} \equiv x \pmod {P}\)。可以转化为 \(p \equiv qx \pmod {P}\)。
那么可以 BSGS。设一个阈值 \(B\)，假设 \(q = aB + b\)，那么 \(p \equiv aBx + bx \pmod {P}\)。我们接下来先枚举 \(a\)，将 \(aBx\) 使用一个数据结构存下来。
接下来我们枚举 \(b\)，想要知道对于这个 \(b\) 有没有满足条件的 \(a\)。然后由于 \(aBx < 2P\)，所以 \(aBx + bx \isin [0, V]\) 或 \([P, P+V]\)，也就是查询是否存在 \([0, V - bx] \cup [P - bx, P + V - bx]\) 的范围内是否存在我们已经存好的 \(aBx\)。
我们可以把 \(aBx\) 排序一下，然后在上面二分，就可以得到是否有在给定范围内的 \(aBx\) 了。
那么这道题就做完了，理论上 \(B = \sqrt V\)，复杂度可以到达 \(O(n + \sqrt V \log V)\)。实际上 \(B = 10^4\) 较快。
要卡常，快读是贺 Purslane 的。
#include<bits/stdc++.h>
#define endl '\n'
#define N 1000006
using namespace std;
using i64=long long;
using i128=__int128;
constexpr i128 MOD=(i128)9000000000000000041;
constexpr int B=1e4,iB=3e5;
int n,m,_,tot;
i128 t,ma=1,mb=1,val,ival,num[iB+6];
inline void write(i128 k)
{if(k<0)putchar('-'),k=-k;int nnum[40],ttp=0;while(k)nnum[++ttp]=k%10,k/=10;if(!ttp)nnum[++ttp]=0;while(ttp)putchar(nnum[ttp--]^48);
}
class IO_helper{ // by purslane
private:static const int L = 1 << 16;char in_buf[L], *in_st, *out_st;char _getc(){if (in_st == out_st){out_st = (in_st = in_buf) + fread(in_buf, 1, L, stdin);if (in_st == out_st) return EOF;}return *in_st++;}
public:template <typename IntType>IO_helper &operator>>(IntType &x){bool ok=0;char c; while ((c = _getc()) < '0' || c > '9')ok|=c=='-';for (x = 0; c >= '0' && c <= '9'; c = _getc())x = x * 10 + c - '0';x=(ok?-x:x);return *this;}
} IO;
i128 qpow(i128 x,i128 y=MOD-2)
{i128 ret=1;for(;y;y>>=1,x=x*x%MOD)if(y&1)ret=ret*x%MOD;return ret;
}
i128 gcd128(i128 x,i128 y) {return y?gcd128(y,x%y):x;}
int check(i128 p)
{i128 q=ival*p%MOD;if(p&&q&&p<=3e9&&q<=3e9){i128 g=gcd128(p,q);p/=g,q/=g,write(p),putchar(32),write(q),putchar(10);return 1;}return 0;
}
int lb(i128 x)
{int l=1,r=tot,ret=tot+1;while(l<=r){int mid=l+r>>1;if(num[mid]>x)ret=mid,r=mid-1;else l=mid+1;}return ret;
}
main()
{IO>>n>>m>>_;for(int i=1;i<=n;i++)IO>>t,ma=ma*t%MOD;for(int i=1;i<=m;i++)IO>>t,mb=mb*t%MOD;val=ma*qpow(mb)%MOD,ival=qpow(val);for(int i=0;i<iB;i++)num[++tot]=i*B*val%MOD;sort(num+1,num+1+tot);for(int i=0,it;i<B;i++){i128 b=(MOD-i*val%MOD)%MOD;it=lb(b);if(it<=tot&&check((i*val+num[it])%MOD))return 0;it=lb(0);if(it<=tot&&check((i*val+num[it])%MOD))return 0;}write(val),printf(" 1\n");return 0;
}