#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#include <sys/mman.h>
#include <unistd.h>
#include <bitset>

char*rp;

inline int rd_int(){
	int v=0;
	for(int c;c=*rp++-48,c>=0;)v=v*10+c;
	return v;
}

int n,k;

struct RangeVal {
	int st;
	int ed;
	int val;
};
RangeVal rv[30000],rvtmp[30000];

char wbuf[30000];

typedef std::bitset<15001> bst;

void f(int st,int ed,int l,int r,bst& bs){
	int tmpn=0,wn=l;
	for(int i=l;i<r;++i){
		if(rv[i].ed<=st||ed<=rv[i].st){
			rvtmp[tmpn++]=rv[i];
		}else if(rv[i].st<=st&&ed<=rv[i].ed){
			bs|=bs<<rv[i].val;
			rvtmp[tmpn++]=rv[i];
		}else{
			rv[wn++]=rv[i];
		}
	}
	for(int i=0;i<tmpn;++i){
		rv[wn+i]=rvtmp[i];
	}
	if(st==ed-1){
		wbuf[st*2+0]=bs[k]+48;
		wbuf[st*2+1]=10;
	}else{
		bst bs1=bs;
		f(st,st+ed>>1,l,wn,bs1);
		f(st+ed>>1,ed,l,wn,bs);
	}
}

int main(){
	rp=static_cast<char*>(mmap(0,1l<<28,1,2,0,0));
	n=rd_int();
	k=rd_int();
	for(int i=0;i<n;++i){
		rv[i]={0,15000,rd_int()};
	}
	int q=rd_int();
	for(int i=0;i<q;++i){
		int x=rd_int()-1;
		int v=rd_int();
		rv[n+i]={rv[x].st,i,rv[x].val};
		rv[x]={i,rv[x].ed,v};
	}

	bst bs;
	bs[0]=1;
	f(0,q,0,n+q,bs);
	write(1,wbuf,q*2);
	_exit(0);
}