#include <bits/stdc++.h>
#define int long long

using namespace std;

constexpr int MAXN = 500005;

int n, k, t, p, v, Q;
int q[MAXN], a[MAXN], f[MAXN], g[MAXN], h[MAXN];
char s[MAXN];

void dp(int f[]) {
	deque < pair <int, int> > hp;

	f[0] = 0;
	hp.push_back(make_pair(0, 0));

	for(int i = 1; i <= n + 1; i++) {
		while(hp.front().second < i - k) {
			hp.pop_front();
		}

		f[i] = hp.front().first + a[i];
		if(s[i] == '1') {
			hp.clear();
		}

		while(!hp.empty() && hp.back().first >= f[i]) {
			hp.pop_back();
		}
		hp.push_back(make_pair(f[i], i));
	}
}

int dp2(int x, int y) {
	int tmp = a[x];
	a[x] = y;

	int res = 8E18;
	deque < pair <int, int> > dq;
	for(int i = k; i > 0; i--) {
		if(x - i >= 0) {
			if(s[x - i] == '1') {
				dq.clear();
			}
			while(!dq.empty() && dq.back().first >= f[x - i]) {
				dq.pop_back();
			}
			dq.push_back(make_pair(f[x - i], x - i));
		}
	}

	for(int i = x; i < x + k && i <= n + 1; i++) {
		while(dq.front().second < i - k) {
			dq.pop_front();
		}

		h[i] = dq.front().first + a[i];
		res = min(res, h[i] + g[i]);

		if(s[i] == '1') {
			dq.clear();
		}

		while(!dq.empty() && dq.back().first >= h[i]) {
			dq.pop_back();
		}

		dq.push_back(make_pair(h[i], i));
	}

	a[x] = tmp;
	return res;
}

void solve() {
	cin >> n >> k;
	a[n + 1] = 0;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	cin >> (s + 1);

	dp(f);

	reverse(a + 1, a + n + 1);
	reverse(s + 1, s + n + 1);
	dp(g);

	reverse(a + 1, a + n + 1);
	reverse(s + 1, s + n + 1);
	reverse(g, g + n + 2);

	for(int i = 1; i <= n; i++) {
		g[i] -= a[i];
	}

	cin >> Q;
	while(Q--) {
		int x, y;
		cin >> x >> y;

		cout << dp2(x, y) << '\n';
	}
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while(t--) {
        solve();
    }

    return 0;
}

answer.code: In function ‘void solve()’:
answer.code:83:13: error: no match for ‘operator>>’ (operand types are ‘std::istream’ {aka ‘std::basic_istream<char>’} and ‘char*’)
   83 |         cin >> (s + 1);
      |         ~~~ ^~ ~~~~~~~
      |         |         |
      |         |         char*
      |         std::istream {aka std::basic_istream<char>}
In file included from /usr/include/c++/14/sstream:40,
                 from /usr/include/c++/14/complex:45,
                 from /usr/include/c++/14/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:127,
                 from answer.code:1:
/usr/include/c++/14/istream:170:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(bool&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’ (near match)
  170 |       operator>>(bool& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:170:7: note:   conversion of argument 1 would be ill-formed:
answer.code:83:19: error: cannot bind non-const lvalue reference of type ‘bool&’ to a value of type ‘char*’
   83 |         cin >> (s + 1);
      |                ~~~^~~~
/usr/include/c++/14/istream:174:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(short int&) [with _CharT = char; _Traits = std::char_traits<char>]’ (near match)
  174 |       operator>>(short& __n);
      |       ^~~~~~~~
/usr/include/c++/14/istream:174:7: note:   conversion of argument 1 would be ill-formed:
answer.code:83:19: error: invalid conversion from ‘char*’ to ‘short int’ [-fpermissive]
   83 |         cin >> (s + 1);
      |                ~~~^~~~
      |                   |
      |                   char*
answer.code:83:19: error: cannot bind rvalue ‘(short int)(((char*)(& s)) + 1)’ to ‘short int&’
/usr/include/c++/14/istream:177:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(short unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’ (near match)
  177 |       operator>>(unsigned short& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:177:7: note:   conversion of argument 1 would be ill-formed:
answer.code:83:19: error: invalid conversion from ‘char*’ to ‘short unsigned int’ [-fpermissive]
   83 |         cin >> (s + 1);
      |                ~~~^~~~
      |                   |
      |                   char*
answer.code:83:19: error: cannot bind rvalue ‘(short unsigned int)(((char*)(& s)) + 1)’ to ‘short unsigned int&’
/usr/include/c++/14/istream:181:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(int&) [with _CharT = char; _Traits = std::char_traits<char>]’ (near match)
  181 |       operator>>(int& __n);
      |       ^~~~~~~~
/usr/include/c++/14/istream:181:7: note:   conversion of argument 1 would be ill-formed:
answer.code:83:19: error: invalid conversion from ‘char*’ to ‘int’ [-fpermissive]
   83 |         cin >> (s + 1);
      |                ~~~^~~~
      |                   |
      |                   char*
answer.code:83:19: error: cannot bind rvalue ‘(int)(((char*)(& s)) + 1)’ to ‘int&’
/usr/include/c++/14/istream:184:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’ (near match)
  184 |       operator>>(unsigned int& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:184:7: note:   conversion of argument 1 would be ill-formed:
answer.code:83:19: error: invalid conversion from ‘char*’ to ‘unsigned int’ [-fpermissive]
   83 |         cin >> (s + 1);
      |                ~~~^~~~
      |                   |
      |                   char*
answer.code:83:19: error: cannot bind rvalue ‘(unsigned int)(((char*)(& s)) + 1)’ to ‘unsigned int&’
/usr/include/c++/14/istream:188:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’ (near match)
  188 |       operator>>(long& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:188:7: note:   conversion of argument 1 would be ill-formed:
answer.code:83:19: error: invalid conversion from ‘char*’ to ‘long int’ [-fpermissive]
   83 |         cin >> (s + 1);
      |                ~~~^~~~
      |                   |
      |                   char*
answer.code:83:19: error: cannot bind rvalue ‘(long int)(((char*)(& s)) + 1)’ to ‘long int&’
/usr/include/c++/14/istream:192:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long unsigned int&) [with _CharT = cha...