#define NDEBUG
#include <bits/stdc++.h>

using llsi = long long signed int;

std::vector<int> get_z(const std::string &s) {
	std::vector<int> z(s.size());
	size_t n = z[0] = s.size();
	for(int i = 1, l = -1, r = -1; i < n; ++i) {
		if(i >= r) r = i;
		else if(i + z[i - l] < r) {
			z[i] = z[i - l];
			continue;
		}
ext:	l = i;
		while(r < n && s[r] == s[r - l]) r += 1;
		z[i] = r - l;
	}
	return z;
}

std::vector<int> prefix_match(const std::string &s, const std::string &t) {
	std::vector<int> z = get_z(t), res(s.size());
	size_t n = s.size(), m = t.size();
	for(int i = 0, l = -1, r = -1; i < n; ++i) {
		if(i >= r) r = i;
		else if(i + z[i - l] < r) {
			res[i] = z[i - l];
			continue;
		}
ext:	l = i;
		while(r < n && r - l < m && s[r] == t[r - l]) r += 1;
		res[i] = r - l;
	}
	return res;
}

std::vector<int> get_fail(const std::string &s) {
	std::vector<int> fail(s.size());
	size_t n = s.size();
	fail[0] = -1;
	for(int i = 1, j = -1; i < n; ++i) {
		while(~j && s[j + 1] != s[i]) j = fail[j];
		if(s[j + 1] == s[i]) j += 1;
		fail[i] = j;
	}
	return fail;
}

std::vector<int> suffix_match(const std::string &s, const std::string &t) {
	std::vector<int> fail = get_fail(t), res(s.size());
	size_t n = s.size(), m = t.size();
	for(int i = 0, j = -1; i < n; ++i) {
		while(~j && t[j + 1] != s[i]) j = fail[j];
		if(t[j + 1] == s[i]) j += 1;
		res[i] = j + 1;
	}
	return res;
}

void work() {
	int n, q, B;
	std::cin >> n >> q;
	B = std::sqrt(n * std::__lg(n));
	std::string s, t;
	std::cin >> s >> t;
	std::vector<llsi> w(n), sw(n), fw(n), ans(q), top(n);
	std::vector<int> pm = prefix_match(t, s);
	std::vector<int> sm = suffix_match(t, s);
	std::vector<int> f = get_fail(s);
	
	
	std::vector<std::array<int, 3>> query(q);
	std::vector<int> BB(n, 0);
	for(int i = B; i < n; ++i) BB[i] = BB[i - B] + 1;
	
	for(int i = 0; i < n; ++i) {
		std::cin >> w[i];
		sw[i] = fw[i] = w[i];
		if(i > 0) sw[i] += sw[i - 1];
		
		if(f[i] >= 0) fw[i] += fw[f[i]];
	}
	
	top[0] = -1;
	
	for(int i = 1; i < n; ++i) {
		if(f[i] < 0 || i - f[i] != f[i] - f[f[i]]) top[i] = f[i];
		else                                       top[i] = top[f[i]];
	}
	
//	for(int i = 0; i < n; ++i) std::cerr << f[i] << char(i == n - 1 ? 10 : 32);
//	for(int i = 0; i < n; ++i) std::cerr << top[i] << char(i == n - 1 ? 10 : 32);
//	
//	return ;
	
	for(auto &[l, r, _]: query) std::cin >> l >> r, l -= 1, r -= 1;
	for(int i = 0; i < q; ++i) query[i][2] = i;
	std::sort(query.begin(), query.end(), [&](
		const std::array<int, 3> &x,
		const std::array<int, 3> &y
	) {
		auto [xl, xr, xi] = x;
		auto [yl, yr, yi] = y;
//		assert(0 <= xl && xl < n);
//		assert(0 <= yl && yl < n);
		return BB[xl] == BB[yl]
			? xr < yr
			: BB[xl] < BB[yl];
	});
	
	auto fetch_right = [&] (int l, int r) -> llsi {
		int s = sm[r] - 1;
		
		while(top[s] + 1 > r - l + 1) s = top[s];
		
		if(s + 1 > r - l + 1) {
			int dlt = s - f[s];
			s -= (s - (r - l) + (dlt - 1)) / dlt * dlt;
		}
		assert(s + 1 <= r - l + 1);
		
		return s < 0 ? 0 : fw[s];
	};
	
//	for(int i = 0; i < n; ++i)
//		std::cerr << sm[i] << char(i == n - 1 ? 10 : 32);
//	
//	for(int i = 0; i < n; ++i)
//		for(int j = i; j < n; ++j)
//			std::cerr << fetch_right(i, j) << char(j == n - 1 ? 10 : 32);
//	return ;
		
	int l = 0, r = -1;
	llsi cans = 0;
	for(auto [ql, qr, id]: query) {
		while(l > ql) {
			--l;
			auto t = std::min(pm[l], r - l + 1);
			assert(t <= n);
			cans += t > 0 ? sw[t - 1] : 0;
		}
		while(r < qr) {
			++r;
			cans += fetch_right(l, r);
		}
		while(l < ql) {
			auto t = std::min(pm[l], r - l + 1);
			assert(t <= n);
			cans -= t > 0 ? sw[t - 1] : 0;
			l++;
		}
		while(r > qr) {
			cans -= fetch_right(l, r);
			r--;
		}
		ans[id] = cans;
	}
	for(int i = 0; i < q; ++i) std::cout << ans[i] << char(10);
	
	return ;
}

int main() {
	// freopen("1.in", "r", stdin);
	std::ios::sync_with_stdio(false);
	int T = 1; while(T--) work();
	return 0;
}