#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=500005;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,K,a[N],pre[N],suf[N];
char s[N];
ll f[N],g[N],ff[N],gg[N];
int Q[N],L,R;
int read() {
	int x=0,f=1; char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-48;
	return x*f;
}
void solve() {
    n=read(); K=read();
    for(int i=1;i<=n;i++) a[i]=read();
    scanf("%s",s+1);
    for(int i=2;i<=n;i++) {
        pre[i]=pre[i-1];
        if(s[i-1]=='1') pre[i]=i-1;
    }
    suf[n]=n+1;
    for(int i=n-1;i>=1;i--) {
        suf[i]=suf[i+1];
        if(s[i+1]=='1') suf[i]=i+1;
    }
    Q[L=R=1]=0;
    for(int i=1;i<=n;i++) {
        while(Q[L]<pre[i]||i-Q[L]>K) L++;
        f[i]=f[Q[L]]+a[i];
        while(L<=R&&f[i]<=f[Q[R]]) R--;
        Q[++R]=i;
    }
    g[n+1]=0; Q[L=R=1]=n+1;
    for(int i=n;i>=1;i--) {
        while(Q[L]>suf[i]||Q[L]-i>K) L++;
        g[i]=g[Q[L]]+a[i];
        while(L<=R&&g[i]<=g[Q[R]]) R--;
        Q[++R]=i;
    }
    for(int q=read();q--;) {
        int x=read(),v=read();
        if(s[x]=='1') printf("%lld\n",f[x]+g[x]-2*a[x]+v);
        else {
            if(suf[x]-pre[x]<=K) {
                printf("%lld\n",f[pre[x]]+g[pre[x]]-a[pre[x]]);
                continue;
            }
            int l=max(x-K,pre[x]),r=min(x+K,suf[x]);
            for(int i=l;i<=r;i++) ff[i]=f[i],gg[i]=g[i];
            
            L=1; R=0;
            for(int i=l;i<x;i++) {
                while(L<=R&&ff[i]<=ff[Q[R]]) R--;
                Q[++R]=i;
            }
            ff[x]=ff[Q[L]]+v;
            while(L<=R&&ff[x]<=ff[Q[R]]) R--;
            Q[++R]=x;
            for(int i=x+1;i<=r;i++) {
                while(i-Q[L]>K) L++;
                ff[i]=ff[Q[L]]+a[i];
                while(L<=R&&ff[i]<=ff[Q[R]]) R--;
            }
            
            L=1; R=0;
            for(int i=r;i>x;i--) {
                while(L<=R&&gg[i]<=gg[Q[R]]) R--;
                Q[++R]=i;
            }
            gg[x]=gg[Q[L]]+v;
            while(L<=R&&gg[x]<=gg[Q[R]]) R--;
            Q[++R]=x;
            for(int i=x-1;i>=l;i--) {
                while(Q[L]-i>K) L++;
                gg[i]=gg[Q[L]]+a[i];
                while(L<=R&&gg[i]<=gg[Q[R]]) R--;
            }
            
            ll ans=INF;
            int o=a[x]; a[x]=v;
            for(int i=l;i<=r;i++) ans=min(ans,ff[i]+gg[i]-a[i]);
            a[x]=o;
            printf("%lld\n",ans);
        }
    }
}
int main() {
    for(int T=read();T--;) solve();
    return 0;
}