#include<cstdio>
#include<queue>
#include<algorithm>
#define ll long long
#define LPos (Pos<<1)
#define RPos (LPos|1)
#define Mid ((L+R)>>1)
using namespace std;
ll Read()
{
	ll Output=0;
	char Input=getchar();
	while(Input<'0'||Input>'9')
	Input=getchar();
	while(Input>='0'&&Input<='9')
	{
		Output=Output*10+Input-'0';
		Input=getchar();
	}
	return Output;
}
int T;
ll A[500010];
int N,K;
char String[500010];
ll Prefix[500010],Suffix[500010];
int Queue[500010],Left,Right;
void Solve()
{
    N=Read(),K=Read();
    for(int i=1;i<=N;++i)
    A[i]=Read();
    A[N+1]=0;
    int Last=0;
    Queue[Right=1]=0;
    Left=1;
    Suffix[N+1]=Prefix[0]=0;
    scanf("%s",String+1);
    String[0]=String[N+1]='1';
    for(int i=1;i<=N+1;++i)
    {
        Last=max(Last,i-K);
        while(Left<=Right&&Queue[Left]<Last)
        ++Left;
        Prefix[i]=Prefix[Queue[Left]]+A[i];
        if(String[i]=='1')
        Last=i;
        while(Left<=Right&&Prefix[i]<=Prefix[Queue[Right]])
        --Right;
        Queue[++Right]=i;
    }
    Queue[Right=1]=N+1;
    Left=1,Last=N+1;
    for(int i=N;i>=0;--i)
    {
        Last=min(Last,i+K);
        while(Left<=Right&&Queue[Left]>Last)
        ++Left;
        Suffix[i]=Suffix[Queue[Left]]+A[i];
        if(String[i]=='1')
        Last=i;
        while(Left<=Right&&Suffix[i]<=Suffix[Queue[Right]])
        --Right;
        Queue[++Right]=i;
    }
    int Q=Read();
    for(int i=1;i<=Q;++i)
    {
        int P=Read(),V=Read();
        ll Ans=Prefix[P]+Suffix[P]-(A[P]<<1)+V;
        if(String[P]=='1')
        {
            printf("%lld\n",Ans);
            continue;
        }
        Queue[Right=1]=max(P-K+1,0);
        for(int j=max(P-K+1,0);j<P;++j)
        {
            while(Right&&Prefix[j]<=Prefix[Queue[Right]])
            --Right;
            Queue[++Right]=j;
        }
        Left=1;
        for(int j=P+1;j<=P+K-1&&j<=N+1;++j)
        {
            while(j-Queue[Left]>K)
            ++Left;
            Ans=min(Ans,Prefix[Queue[Left]]+Suffix[j]);
        }
        printf("%lld\n",Ans);
    }
// puts("Pre");
// for(int i=0;i<=N+1;++i)
// printf("%lld ",Prefix[i]);
// puts("\nSuf");
// for(int i=0;i<=N+1;++i)
// printf("%lld ",Suffix[i]);
// putchar('\n');
}
int main()
{
	T=Read();
    while(T--)
    {
        // Clear();
        Solve();
    }
}