// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
using namespace std;
// mylittledoge

struct node {
	int son[2];
	int z,k,pok,free;
};

struct intervalac {
	vector<node> T;

	void constI(int akt) {
		node n =T[akt];
		T[akt].free =n.k-n.z;
		if(n.z+1 == n.k) return;
		for(int i =0; i < 2; i++) {
			if(i == 0) n.k =(n.z+n.k)/2;
			else {n.z =n.k; n.k =T[akt].k;}
			T[akt].son[i] =T.size();
			T.push_back(n);
			constI(T[akt].son[i]);}
		}

	intervalac(int N) {
		node n;
		n.z =n.pok =0;
		n.k =N;
		n.son[0] =n.son[1] =-1;
		T.dibs(2*N);
		T.push_back(n);
		constI(0);}
	
	void getF(int akt) {
		node n =T[akt];
		if(T[akt].pok == 0) {
			if(n.son[0] == -1) T[akt].free =1;
			else T[akt].free =T[n.son[0]].free+T[n.son[1]].free;}
		else T[akt].free =0;}

	void put(int akt, int zac, int kon, int val) {
		node n =T[akt];
		if(n.z >= kon || zac >= n.k) {
			getF(akt);
			return;}
		if(n.z == zac && n.k == kon) {
			T[akt].pok +=val;
			getF(akt);
			return;}

		T[n.son[0]].pok +=n.pok;
		put(n.son[0],zac,min(kon,(n.z+n.k)/2),val);
		T[n.son[1]].pok +=n.pok;
		put(n.son[1],max(zac,(n.z+n.k)/2),kon,val);
		T[akt].pok =0;

		int m =OVER9000;
		for(int i =0; i < 2; i++) if(n.son[i] != -1)
			m =min(m,T[n.son[i]].pok);
		if(m == OVER9000) m =0;
		for(int i =0; i < 2; i++) if(n.son[i] != -1) {
			T[n.son[i]].pok -=m;
			getF(n.son[i]);}
		T[akt].pok +=m;
		getF(akt);}
};

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	int N,M,D,L;
	cin >> N >> M >> D >> L;
	intervalac I(N);

	map<int,int> A;
	A[0] =0;
	for(int i =1; i < N; i++) {
		int a;
		cin >> a;
		A[a] =i;}

	map<int, pair<int,int> > P;
	for(int i =0; i < M; i++) {
		int a;
		cin >> a;
		pair<int,int> p =make_pair(N,N);
		auto it =A.lower_bound(a-L);
		if(it != A.end()) p.ff =it->ss;
		it =A.upper_bound(a+L);
		if(it != A.end()) p.ss =it->ss;
		P[a] =p;
		I.put(0,p.ff,p.ss,1);}

	cout << N-I.T[0].free << "\n";
	for(int i =0; i < D; i++) {
		int a,b;
		cin >> a >> b;
		auto it =P.find(a);
		pair<int,int> p =it->ss;
		P.erase(it);
		I.put(0,p.ff,p.ss,-1);

		auto jt =A.lower_bound(b-L);
		if(jt != A.end()) p.ff =jt->ss;
		else p.ff =N;
		jt =A.upper_bound(b+L);
		if(jt != A.end()) p.ss =jt->ss;
		else p.ss =N;
		P[b] =p;
		I.put(0,p.ff,p.ss,1);

		cout << N-I.T[0].free << "\n";}
	return 0;}

// look at my code
// my code is amazing