#include <bits/stdc++.h>
#define N (1000000 + 10)  /*------------------ #define ------------------*/
#define M (400000 + 10)
#define MOD (1000000000 + 7)
//#define MOD (998244353)
#define INF (0x3f3f3f3f)
#define LNF (3e18)
#define mod(a,b) (((a)%(b)+(b))%(b))
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL,LL> PII;
typedef pair<LL,LL> PLL;
typedef pair<LL,LL> PIL;
typedef pair<LL,LL> PLI;
typedef pair<double,double> PDD;

LL n,k;
LL a[N],f[N],g[N],tmp[N];
string st;
LL q[N];

auto solve(){
	
	cin >> n >> k;
	for(LL i = 0;i <= n + 10;i ++ ) f[i] = g[i] = tmp[i] = q[i] = 0;
	for(LL i = 1;i <= n;i ++ ) cin >> a[i];
	cin >> st;
	st = '1' + st + '1';
	
	LL hh = 0,tt = -1;
	q[++ tt] = 0;
	for(LL i = 1;i <= n + 1;i ++ ){
		while(hh <= tt && q[hh] < i - k) hh ++ ;
		f[i] = f[q[hh]] + a[i];
		if(st[i] == '0'){
			while(hh <= tt && f[q[tt]] >= f[i]) tt -- ;
		}else{
			while(hh <= tt) tt -- ;
		}
		q[++ tt] = i;
	}
	
	hh = 0,tt = -1;
	q[++ tt] = n + 1;
	for(LL i = n;i >= 0;i -- ){
		while(hh <= tt && q[hh] > i + k) hh ++ ;
		g[i] = g[q[hh]] + a[i];
		if(st[i] == '0'){
			while(hh <= tt && g[q[tt]] >= g[i]) tt -- ;
		}else{
			while(hh <= tt) tt -- ;
		}
		q[++ tt] = i;
	}
	
	// for(LL i = 0;i <= n + 1;i ++ ) cout << f[i] << ' ';
	// cout << '\n';
// 	
	// for(LL i = 0;i <= n + 1;i ++ ) cout << g[i] << ' ';
	// cout << '\n';
// 	
	// cout << "==========\n";
	
	LL Q;
	cin >> Q;
	while(Q -- ){
		LL p,v,tv;
		cin >> p >> v;
		tv = a[p];
		for(LL i = max(p - k + 1,0);i <= min(p + k,n + 1);i ++ )
			tmp[i] = f[i];
		f[p] = f[p] - a[p] + v;
		a[p] = v;
		
		hh = 0,tt = -1;
		for(LL i = max(p - k + 1,0);i <= p;i ++ ){
			while(hh <= tt && q[hh] > i + k) hh ++ ;
			if(st[i] == '0'){
				while(hh <= tt && f[q[tt]] >= f[i]) tt -- ;
			}else{
				while(hh <= tt) tt -- ;
			}
			q[++ tt] = i;
		}
		for(LL i = p + 1;i <= min(p + k,n + 1);i ++ ){
			while(hh <= tt && q[hh] < i - k) hh ++ ;
			// if(i == 4){
				// cout << '\n';
				// for(LL j = hh;j <= tt;j ++ ) cout << q[j] << ' ';
				// cout << '\n';
			// }
			f[i] = f[q[hh]] + a[i];
			//if(i == 4) cout << i << ' ' << f[i] << '\n';
			if(st[i] == '0'){
				while(hh <= tt && f[q[tt]] >= f[i]) tt -- ;
			}else{
				while(hh <= tt) tt -- ;
			}
			q[++ tt] = i;
		}
		
		// for(LL i = 0;i <= n + 1;i ++ ) cout << f[i] << ' ';
		// cout << '\n';
// 		
		// for(LL i = 0;i <= n + 1;i ++ ) cout << g[i] << ' ';
		// cout << '\n';
		
		LL ans = 2e9;
		for(LL i = p + 1;i <= min(p + k,n + 1);i ++ )
			ans = min(ans,f[i] + g[i] - a[i]);
		cout << ans << '\n';
		
		a[p] = tv;
		for(LL i = max(p - k + 1,0);i <= min(p + k,n + 1);i ++ )
			f[i] = tmp[i];
	}
}

signed main(){
	IOS
	LL T = 1;
	//
	cin >> T;
	while(T -- ) solve();
	//while(T -- ) cout << (solve() ? "YES" : "NO") << '\n';

    return 0;
}

answer.code: In function ‘auto solve()’:
answer.code:74:31: error: no matching function for call to ‘max(LL, int)’
   74 |                 for(LL i = max(p - k + 1,0);i <= min(p + k,n + 1);i ++ )
      |                            ~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from answer.code:1:
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)’
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
answer.code:74:31: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘int’)
   74 |                 for(LL i = max(p - k + 1,0);i <= min(p + k,n + 1);i ++ )
      |                            ~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note:   template argument deduction/substitution failed:
answer.code:74:31: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘int’)
   74 |                 for(LL i = max(p - k + 1,0);i <= min(p + k,n + 1);i ++ )
      |                            ~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)’
 5795 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note:   template argument deduction/substitution failed:
answer.code:74:31: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘long long int’
   74 |                 for(LL i = max(p - k + 1,0);i <= min(p + k,n + 1);i ++ )
      |                            ~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)’
 5805 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note:   template argument deduction/substitution failed:
answer.code:74:31: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘long long int’
   74 |                 for(LL i = max(p - k + 1,0);i <= min(p + k,n + 1);i ++ )
      |                            ~~~^~~~~~~~~~~~~
answer.code:80:31: error: no matching function for call to ‘max(LL, int)’
   80 |                 for(LL i = max(p - k + 1,0);i <= p;i ++ ){
      |                            ~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)’
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
answer.code:80:31: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘int’)
   80 |                 for(LL i = max(p - k + 1,0);i <= p;i ++ ){
      |                            ~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note:   template argument deduction/substitution failed:
answer.code:80:31: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘int’)
   80 |                 for(LL i = max(p - k + 1,0);i <= p;i ++ ){
      |                            ~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)’
 5795 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note:   template argument deduction/substitution failed:
answer.code:80:31: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘long long int’
   80 |                 for(LL i = max(p - k + 1,0);i <= p;i ++ ){
      |                            ~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)’
 5805 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note:   template argument deduction/substitution failed:
answer.code:80:31: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘long long int’
   80 |                 for(LL i = max(p - k + 1,0);i <= p;i ++ ){
      |          ...