题目意思比较难描述，但是易懂…
我们考虑到这是一个匹配问题，转换一下。
由于题目说了是 (a_i + c_j leq z) ， (i) 和 (j) 有一条边，那么发现 (a_i) 不变，我们就可以给 (a_i) 排序，然后因为数值是有单调性的，如果 (a_i + c_j leq z) ，那么 (a_k(1 leq kleq i)+ c_j leq z)。
那么我们想一个这个问题的转化: 给你 (n) 个位置 (m) 个物品，每个位置仅仅能放一个物品，第 (i) 个物品有一个限制，只能放到 ([1,p_i]) 里面，求最多能放多少个物品。
容易证明，如果用 不基于排序 的做法做出这个转化版问题，就可以带上莫队做出这个原问题。
我们想，假设你能放 (k) 个物品，采用最优策略。
那么你 (p_i) 一定是选前 (k) 大的，依次放到 (1…k)。
第 (k) 大的放在位置 (1)，那么显然 (p_k geq 1)
第 (k-1) 大的放在位置 (2)，那么 (p_{k-1}geq 2)
……
第 (k + x - 1) 大的物品放在位置 (x) ，那么 (p_{k+x-1}geq x)
也就是说 (p_x + x - 1 geq k)
而 (x) 指的是区间第 (x) 大，就是有多少个数比他要大，而你可以通过线段树，对于每个 (p_i) ，区间加 ([1,p_i])
由于 (k) 要满足所有条件，所以要取最小值。
// powered by c++11
// by Isaunoya
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize(
"inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2,-ffast-math,-fsched-spec,unroll-loops,-falign-jumps,-falign-loops,-falign-labels,-fdevirtualize,-fcaller-saves,-fcrossjumping,-fthread-jumps,-funroll-loops,-freorder-blocks,-fschedule-insns,inline-functions,-ftree-tail-merge,-fschedule-insns2,-fstrict-aliasing,-fstrict-overflow,-falign-functions,-fcse-follow-jumps,-fsched-interblock,-fpartial-inlining,no-stack-protector,-freorder-functions,-findirect-inlining,-fhoist-adjacent-loads,-frerun-cse-after-loop,inline-small-functions,-finline-small-functions,-ftree-switch-conversion,-foptimize-sibling-calls,-fexpensive-optimizations,inline-functions-called-once,-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); ++i)
#define Rep(i, x, y) for (register int i = (x); i >= (y); --i)
using namespace std;
using db = double;
using ll = long long;
using uint = unsigned int;
#define Tp template
using pii = pair<int, int>;
#define fir first
#define sec second
Tp<class T> void cmax(T& x, const T& y) {if (x < y) x = y;} Tp<class T> void cmin(T& x, const T& y) {if (x > y) x = y;}
#define all(v) v.begin(), v.end()
#define sz(v) ((int)v.size())
#define pb emplace_back
Tp<class T> void sort(vector<T>& v) { sort(all(v)); } Tp<class T> void reverse(vector<T>& v) { reverse(all(v)); }
Tp<class T> void unique(vector<T>& v) { sort(all(v)), v.erase(unique(all(v)), v.end()); }
const int SZ = 1 << 23 | 233;
struct FILEIN { char qwq[SZ], *S = qwq, *T = qwq, ch;
#ifdef __WIN64
#define GETC getchar
#else
char GETC() { return (S == T) && (T = (S = qwq) + fread(qwq, 1, SZ, stdin), S == T) ? EOF : *S++; }
#endif
FILEIN& operator>>(char& c) {while (isspace(c = GETC()));return *this;}
FILEIN& operator>>(string& s) {while (isspace(ch = GETC())); s = ch;while (!isspace(ch = GETC())) s += ch;return *this;}
Tp<class T> void read(T& x) { bool sign = 0;while ((ch = GETC()) < 48) sign ^= (ch == 45); x = (ch ^ 48);
while ((ch = GETC()) > 47) x = (x << 1) + (x << 3) + (ch ^ 48); x = sign ? -x : x;
}FILEIN& operator>>(int& x) { return read(x), *this; } FILEIN& operator>>(ll& x) { return read(x), *this; }
} in;
struct FILEOUT {const static int LIMIT = 1 << 22 ;char quq[SZ], ST[233];int sz, O;
~FILEOUT() { flush() ; }void flush() {fwrite(quq, 1, O, stdout); fflush(stdout);O = 0;}
FILEOUT& operator<<(char c) {return quq[O++] = c, *this;}
FILEOUT& operator<<(string str) {if (O > LIMIT) flush();for (char c : str) quq[O++] = c;return *this;}
Tp<class T> void write(T x) {if (O > LIMIT) flush();if (x < 0) {quq[O++] = 45;x = -x;}
do {ST[++sz] = x % 10 ^ 48;x /= 10;} while (x);while (sz) quq[O++] = ST[sz--];
}FILEOUT& operator<<(int x) { return write(x), *this; } FILEOUT& operator<<(ll x) { return write(x), *this; }
} out;
int n , m , z , Q ;
const int maxn = 2e5 + 52 ;
int a[maxn] , b[maxn] ;
const int S = 250 ;
int bl[maxn] ;
struct Que {
int l , r , id ;
bool operator < (const Que & other) const {
if(bl[l] != bl[other.l]) return l < other.l ;
return bl[l] & 1 ? r > other.r : r < other.r ;
}
} q[maxn] ;
struct smt {
int t[maxn << 2] , tag[maxn << 2] ;
void build(int l , int r , int p) {
if(l == r) {
t[p] = l ;
return ;
}
int mid = l + r >> 1 ;
build(l , mid , p << 1) ;
build(mid + 1 , r , p << 1 | 1) ;
t[p] = min(t[p << 1] , t[p << 1 | 1]) ;
}
inline void pushdown(int p) {
if(tag[p]) {
tag[p << 1] += tag[p] ;
tag[p << 1 | 1] += tag[p] ;
t[p << 1] += tag[p] ;
t[p << 1 | 1] += tag[p] ;
tag[p] = 0 ;
}
}
void change(int a , int b , int l , int r , int p , int v) {
if(a <= l && r <= b) {
tag[p] += v , t[p] += v ;
return ;
}
pushdown(p) ;
int mid = l + r >> 1 ;
if(a <= mid) change(a , b , l , mid , p << 1 , v) ;
if(b > mid) change(a , b , mid + 1 , r , p << 1 | 1 , v) ;
t[p] = min(t[p << 1] , t[p << 1 | 1]) ;
}
} qwq ;
inline void ins(const int & x) {
int y = b[x] ;
if(y) qwq.change(1 , y , 1 , n , 1 , 1) ;
}
inline void del(const int & x) {
int y = b[x] ;
if(y) qwq.change(1 , y , 1 , n , 1 , -1) ;
}
int ans[maxn] ;
signed main() {
// code begin.
in >> n >> m >> z ;
rep(i , 1 , n) in >> a[i] ; sort(a + 1 , a + n + 1) ; qwq.build(1 , n , 1) ;
rep(i , 1 , m) in >> b[i] ; rep(i , 1 , m) bl[i] = (i - 1) / S + 1 ;
rep(i , 1 , m) b[i] = upper_bound(a + 1 , a + n + 1 , z - b[i]) - a - 1 ;
in >> Q ; rep(i , 1 , Q) in >> q[i].l >> q[i].r , q[i].id = i ;
sort(q + 1 , q + Q + 1) ; int l = 1 , r = 0 ; rep(i , 1 , Q) {
while(l > q[i].l) ins(-- l) ; while(l < q[i].l) del(l ++) ;
while(r < q[i].r) ins(++ r) ; while(r > q[i].r) del(r --) ;
ans[q[i].id] = qwq.t[1] ;
}
rep(i , 1 , Q) out << ans[i] - 1 << '
' ;
return 0;
// code end.
}