#include #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using namespace std; #define ALL(x) begin(x),end(x) #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<bool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(b ostream &operator<<(ostream &os,const vector&v){ for(int i=0;i<(int)v.size();i++) os< istream &operator>>(istream &is,vector&v){ for(T &x:v)is>>x; return is; } struct FastFourierTransform{ using Real = double; using C=complex; const Real PI=acosl(-1); int base; vector rts; vector rev; FastFourierTransform():base(1){ rts.emplace_back(0,0); rts.emplace_back(1,0); rev.push_back(0); rev.push_back(1); } void ensure_base(int nbase){ if(nbase<=base) return; rev.resize(1<>1]>>1)+((i&1)<<(nbase-1)); } while(base &a,int n){ assert((n&(n-1))==0); int zeros=__builtin_ctz(n); ensure_base(zeros); int shift=base-zeros; for(int i=0;i>shift)) swap(a[i],a[rev[i]>>shift]); for(int k=1;k multiply(const vector &a,const vector &b) { int need=(int)a.size()+(int)b.size()-1; int nbase=1; while((1< fa(sz); for(int i=0;i>1)),s(0,1),t(0.5,0); for(int i=0;i<=(sz>>1);i++){ int j=(sz-i)&(sz-1); C z=(fa[j]*fa[j]-conj(fa[i]*fa[i]))*r; fa[j]=(fa[i]*fa[i]-conj(fa[j]*fa[j]))*r; fa[i]=z; } for(int i=0;i<(sz>>1);i++){ C A0=(fa[i]+fa[i+(sz>>1)])*t; C A1=(fa[i]-fa[i+(sz>>1)])*t*rts[(sz>>1)+i]; fa[i]=A0+A1*s; } fft(fa,sz>>1); vector ret(need); for(int i=0;i>1].imag():fa[i>>1].real()); return ret; } }; signed main(){ int N,P;ll K;cin>>N>>K>>P; vector A(P,0),B(P,0); rep(i,N){ int x;cin>>x;A[x]++; } rep(i,N){ int x;cin>>x;B[x]++; } FastFourierTransform FFT; auto C=FFT.multiply(A,B); int S=0; rep(i,P){ S+=C[i]; if(i+P<(int)C.size()) S+=C[i+P]; if(S>=K){ cout<