#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int n,q;
char s[N];
ll dp[N],f[N],sumd[N],summ[N];
int main()
{
    scanf("%d",&n);
    scanf("%s",s+1);
    scanf("%d",&q);
    for(int i=1;i<=n;i++)
    {
        sumd[i]=sumd[i-1]+(s[i]=='D');
        summ[i]=summ[i-1]+(s[i]=='M');
        dp[i]=dp[i-1];
        f[i]=f[i-1];
        if(s[i]=='M') dp[i]+=sumd[i];
        if(s[i]=='C') f[i]+=dp[i];
    }
    while(q--)
    {
        ll ans=f[n];
        int k;scanf("%d",&k);
        for(int i=k;i<=n;i++)
            if(s[i]=='C')
            ans-=dp[i-k]+(summ[i]-summ[i-k])*sumd[i-k];
        printf("%lld\n",ans);
    }
}

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <list>
#include <utility>
#include <tuple>
#include <cstdio>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <cmath>
#define _GLIBCXX_DEBUG
using namespace std;
const long long INF = 1LL << 60;
typedef long long ll;
int main() {
    int A,B,M;
    cin >> A >> B >> M;
    //
    vector<int> a(A);
    for(int i=0;i<A;i++){
        cin >> a[i];
    }
    //
    vector<int> b(B);
    for(int i=0;i<B;i++){
        cin >> b[i];
    }
    //
    vector<int> x(M);
    vector<int> y(M);
    vector<int> c(M);
    for(int i=0;i<M;i++){
        cin >> x[i] >> y[i] >> c[i] ;
    }
    //
    ll price;
    ll min_price;
    for(int i=0;i<M;i++){
        price = a[x[i]-1] + b[y[i]-1] - c[i];
        if(i==0){
            min_price = price;
        }
        else if(min_price > price){
            min_price = price;
        }
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    price = a[0] + b[0];
    if(min_price > price){
        min_price = price;
    }
    cout << min_price << endl;
}