(color{#0066ff}{题解})
#include<bits/stdc++.h>
#define LL long long
LL in() {
char ch; LL x = 0, f = 1;
while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
return x * f;
}
const int maxn = 2e5 + 10;
const int inf = 0x7fffffff;
struct Tree {
protected:
struct node {
node *ch[2];
int l, r, min, tag;
node(int l = 0, int r = 0, int min = 0, int tag = inf): l(l), r(r), min(min), tag(tag) {}
void upd() { min = std::min(ch[0]->min, ch[1]->min); }
void trn(int val) { tag = std::min(tag, val), min = std::min(min, val); }
void dwn() {
if(tag == inf) return;
ch[0]->trn(tag), ch[1]->trn(tag);
tag = inf;
}
int mid() { return (l + r) >> 1; }
}*root;
void build(node *&o, int l, int r, int *a) {
o = new node(l, r, 0);
if(l == r) return(void)(o->min = a[l]);
int mid = (l + r) >> 1;
build(o->ch[0], l, mid, a);
build(o->ch[1], mid + 1, r, a);
o->upd();
}
void lazy(node *o, int l, int r, int val) {
if(l <= o->l && o->r <= r) return (void)(o->trn(val));
o->dwn();
if(l <= o->mid()) lazy(o->ch[0], l, r, val);
if(r > o->mid()) lazy(o->ch[1], l, r, val);
o->upd();
}
int query(node *o, int pos) {
if(o->l == o->r) return o->min;
o->dwn();
if(pos <= o->mid()) return query(o->ch[0], pos);
else return query(o->ch[1], pos);
}
public:
void build(int l, int r, int *a) { build(root, l, r, a); }
void lazy(int l, int r, int val) { lazy(root, l, r, val); }
int query(int pos) { return query(root, pos); }
}s;
int n, m, q, k;
int nxt[maxn][25];
int pre[maxn], ans[maxn];
struct node {
int l, r, id;
node(int l = 0, int r = 0): l(l), r(r) {}
friend bool operator < (const node &a, const node &b) { return a.l < b.l; }
}e[maxn];
int a[maxn], ls[maxn];
bool vis[maxn];
int id(int x) { return x + 10; }
bool judge(int l, int r) {
for(int i = l; i <= r; i++) if(vis[i] || i > n) return false;
return true;
}
void predoit() {
int now = 1;
for(int i = 1; i <= m; i++) {
vis[a[i]] = true;
while(now <= n && !judge(now, now + k - 1)) now++;
ls[i] = now;
}
s.build(1, m, ls);
#ifdef olinr
for(int i = 1; i <= m; i++) printf("%d%c", ls[i], i == m? '
' : ' ');
#endif
for(int i = 1; i <= n; i++) pre[i] = m + 1;
for(int i = m; i >= 1; i--) {
for(int j = -k + 1; j <= k - 1; j++) {
if(a[i] + j >= 1 && a[i] + j <= n)
nxt[i][id(j)] = pre[a[i] + j];
}
pre[a[i]] = i;
}
#ifdef olinr
for(int i = 1; i <= m; i++)
for(int j = -k + 1; j <= k - 1; j++)
if(a[i] + j >= 1 && a[i] + j <= n) printf("after %d, near %d is %d
", i, a[i] + j, nxt[i][id(j)]);
#endif
}
void work() {
std::sort(e + 1, e + q + 1);
int now = 1;
while(now <= q && e[now].l == 1) ans[e[now].id] = s.query(e[now].r), now++;
for(int i = 1; i <= m; i++) {
for(int j = -k + 1; j <= 0; j++) {
if(a[i] + j < 1 || a[i] + j + k - 1 > n) continue;
int min = m + 1;
for(int v = 0; v < k; v++) min = std::min(min, nxt[i][id(j + v)]);
s.lazy(i, min - 1, a[i] + j);
}
while(now <= q && e[now].l <= i + 1) ans[e[now].id] = s.query(e[now].r), now++;
}
}
int main() {
freopen("stall.in", "r", stdin);
freopen("stall.out", "w", stdout);
n = in(), m = in(), q = in(), k = in();
for(int i = 1; i <= m; i++) a[i] = in();
for(int i = 1; i <= q; i++) e[i].l = in(), e[i].r = in(), e[i].id = i;
predoit();
work();
for(int i = 1; i <= q; i++) printf("%d
", ans[i] == n + 1? -1 : ans[i]);
return 0;
}
/*
10 5 15 2
3 1 6 7 5
1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5
*/