#include <iostream>
#include <cstring>
#include <cassert>
#include <vector>
#include <set>
#include <stack>
#include <algorithm>
#include <bitset>
using namespace std;
using B = bitset<300005>;
int main(){
int n;
string s;
cin>>n>>s;
vector<int> len[6];
vector<int> rui[6];
vector<int> two[3][2];
vector<int> subset_dp[3];
vector<int> subset_rmq[3];
vector<int> cnt_up_len[3];
vector<int> cnt_up_two[3][2];
int adj = 0;
vector<pair<int,int>>ch;
for(int i=0;i<n;i++){
if(s[i] != '?'){
ch.emplace_back((s[i]-'A'), i);
}
}
for(int i=1;i<(int)ch.size();i++){
int L = ch[i].second - ch[i-1].second - 1;
int pre = ch[i-1].first;
int nxt = ch[i].first;
adj += (pre != nxt);
if(L){
if(pre == nxt){
len[pre].emplace_back(L);
}
else{
len[pre+nxt+2].emplace_back(L);
}
}
}
for(int i=0;i<6;i++) sort(len[i].begin(), len[i].end());
for(int i=0;i<6;i++){
rui[i].assign(len[i].size()+1, 0);
for(int j=0;j<(int)len[i].size();j++){
rui[i][j+1] = rui[i][j] + len[i][j];
}
}
for(int i=3;i<6;i++){
for(int j=0;j+1<(int)len[i].size();j+=2){
two[i-3][0].emplace_back(len[i][j] + len[i][j+1]);
}
for(int j=1;j+1<(int)len[i].size();j+=2){
two[i-3][1].emplace_back(len[i][j] + len[i][j+1]);
}
}
for(int t=0;t<3;t++){
subset_dp[t].assign(n+1, -1);
int sz = (int)len[t].size();
subset_dp[t][0] = sz;
if(sz == 0) continue;
vector<pair<int,int>>compress;
int pre = len[t][sz-1], cnt = 1;
for(int i=sz-2;i>=-1;i--){
if(i == -1 or pre != len[t][i]){
compress.emplace_back(pre, cnt);
if(i == -1) break;
else{
pre = len[t][i], cnt = 1;
}
}
else cnt ++;
}
B cur; cur.reset();
cur[0] = 1;
constexpr int thres = 10;
int nxt_pos = sz;
for(auto [e,cnt]:compress){
if(cnt >= thres){
for(int i=0;i<e;i++){
int max_good = -1;
vector<pair<int,int>>upd;
for(int j=i;j<=n;j+=e){
if(cur[j]){
max_good = j;
}
else{
if(max_good >= 0 and max_good >= j-cnt*e){
int dp = nxt_pos - (j-max_good) / e;
upd.emplace_back(j, dp);
}
}
}
for(auto [id,dp]:upd){
subset_dp[t][id] = dp;
cur[id] = 1;
}
}
}
else{
for(int i=0;i<cnt;i++){
B nxt = cur | (cur << e);
cur ^= nxt;
for(int j=cur._Find_first();j<cur.size();j=cur._Find_next(j)){
subset_dp[t][j] = nxt_pos-(i+1);
}
swap(cur, nxt);
}
}
nxt_pos -= cnt;
}
auto make = [&](auto self,int id,int l,int r)->void{
if(l == r){
subset_rmq[t][id] = subset_dp[t][l];
return;
}
int m = (l+r)/2;
self(self,id*2+1,l,m);
self(self,id*2+2,m+1,r);
subset_rmq[t][id] = max(subset_rmq[t][id*2+1], subset_rmq[t][id*2+2]);
return;
};
subset_rmq[t].assign(4*n+5, -1);
make(make, 0, 0, n);
}
auto query = [&](auto self,int t,int a,int b,int id,int l,int r)->int{
if(a>b or r<a or b<l) return -1;
if(a<=l and r<=b) return subset_rmq[t][id];
int m=(l+r)/2;
int v1 = self(self,t,a,b,id*2+1,l,m);
int v2 = self(self,t,a,b,id*2+2,m+1,r);
return max(v1,v2);
};
for(int t=0;t<3;t++){
cnt_up_len[t].assign(n+1, 0);
int nxt = 0;
for(int i=0;i<=n;i++){
while(nxt < (int)len[t].size() and len[t][nxt] == i) nxt++;
cnt_up_len[t][i] = nxt;
}
}
for(int t=0;t<3;t++){
for(int p=0;p<2;p++){
if(p == 1 and len[t+3].empty()) continue;
cnt_up_two[t][p].assign(n+1, 0);
int nxt = 0;
for(int i=0;i<=n;i++){
while(nxt < (int)two[t][p].size() and two[t][p][nxt] == i) nxt++;
cnt_up_two[t][p][i] = nxt;
}
}
}
auto func1=[&](int t, int cnt, int l, int r){
if(rui[t].back() == cnt){
if(l == 0) return 0;
else return n;
}
int use = upper_bound(rui[t].begin(), rui[t].end(), cnt) - rui[t].begin();
use --;
int rem = cnt - rui[t][use];
if(query(query,t,l,min(n,r+rem),0,0,n) >= use){
return ((int)len[t].size() - use)*2;
}
else{
return ((int)len[t].size() - use)*2+1;
}
};
auto func2=[&](int x, int y, int s, int t){
int xx = rui[x].back(), yy = rui[y].back(), xy = rui[x+y+2].back();
int scnt = upper_bound(rui[x].begin(), rui[x].end(), s) - rui[x].begin();
int tcnt = upper_bound(rui[y].begin(), rui[y].end(), t) - rui[y].begin();
scnt --; tcnt --;
int ret = n;
for(int p=0;p<2;p++){
if(p == 1 and len[x+y+2].empty()) continue;
int sum = s+t;
if(p == 1 and sum-len[x+y+2][0] < 0) continue;
int lb = -1, ub = n;
while(ub-lb > 1){
int mid = (lb+ub)/2;
if(rui[x][min(scnt, cnt_up_len[x][mid])] + rui[y][min(tcnt, cnt_up_len[y][mid])] + rui[x+y+2][cnt_up_two[x+y-1][p][mid]*2+p] >= sum) ub = mid;
else lb = mid;
}
int cur = rui[x][min(scnt, cnt_up_len[x][ub])] + rui[y][min(tcnt, cnt_up_len[y][ub])] + rui[x+y+2][cnt_up_two[x+y-1][p][ub]*2+p];
int good = min(scnt, cnt_up_len[x][ub])*2 + min(tcnt, cnt_up_len[y][ub])*2 + cnt_up_two[x+y-1][p][ub]*2+p;
if(cur > sum){
int need = (cur-sum);
good -= (need+ub-1)/ub * 2;
}
ret = min(ret, 2*(int)(len[x].size()+len[y].size()) + (int)len[x+y+2].size() - good);
}
return ret;
};
int q; cin>>q;
while(q--){
int x,y,z;
cin>>x>>y>>z;
bool ok = 1;
if(rui[0].back() > x or rui[1].back() > y or rui[2].back() > z) ok = 0;
if(rui[0].back() + rui[3].back() + rui[4].back() < x) ok = 0;
if(rui[1].back() + rui[3].back() + rui[5].back() < y) ok = 0;
if(rui[2].back() + rui[4].back() + rui[5].back() < z) ok = 0;
if(ok){
cout << adj << '\n';
continue;
}
int ans = n;
if(rui[0].back() + rui[3].back() + rui[4].back() <= x){
if(rui[1].back()+rui[5].back() <= y){
int zan = y - rui[1].back() - rui[5].back();
ans = min(ans, func1(2, z, zan, zan));
}
else if(rui[2].back()+rui[5].back() <= z){
int zan = z - rui[2].back() - rui[5].back();
ans = min(ans, func1(1, y, zan, zan));
}
else{
ans = min(ans, func2(1, 2, y, z));
}
}
if(rui[1].back() + rui[3].back() + rui[5].back() <= y){
if(rui[0].back()+rui[4].back() <= x){
int zan = x - rui[0].back() - rui[4].back();
ans = min(ans, func1(2, z, zan, zan));
}
else if(rui[2].back()+rui[4].back() <= z){
int zan = z - rui[2].back() - rui[4].back();
ans = min(ans, func1(0, x, zan, zan));
}
else{
ans = min(ans, func2(0, 2, x, z));
}
}
if(rui[2].back() + rui[4].back() + rui[5].back() <= z){
if(rui[0].back()+rui[3].back() <= x){
int zan = x - rui[0].back() - rui[3].back();
ans = min(ans, func1(1, y, zan, zan));
}
else if(rui[1].back()+rui[3].back() <= y){
int zan = y - rui[1].back() - rui[3].back();
ans = min(ans, func1(0, x, zan, zan));
}
else{
ans = min(ans, func2(0, 1, x, y));
}
}
if(rui[0].back() > x and rui[1].back()+rui[3].back() <= y and rui[2].back()+rui[4].back() <= z){
int remy = y - rui[1].back() - rui[3].back();
int remz = z - rui[2].back() - rui[4].back();
int yz = rui[5].back();
int ymin = remy - min(remy, yz);
int ymax = remy - (yz - min(remz, yz));
ans = min(ans, func1(0, x, ymin, ymax));
}
if(rui[1].back() > y and rui[0].back()+rui[3].back() <= x and rui[2].back()+rui[5].back() <= z){
int remx = x - rui[0].back() - rui[3].back();
int remz = z - rui[2].back() - rui[5].back();
int xz = rui[4].back();
int xmin = remx - min(remx, xz);
int xmax = remx - (xz - min(remz, xz));
ans = min(ans, func1(1, y, xmin, xmax));
}
if(rui[2].back() > z and rui[0].back()+rui[4].back() <= x and rui[1].back()+rui[5].back() <= y){
int remx = x - rui[0].back() - rui[4].back();
int remy = y - rui[1].back() - rui[5].back();
int xy = rui[3].back();
int xmin = remx - min(remx, xy);
int xmax = remx - (xy - min(remy, xy));
ans = min(ans, func1(2, z, xmin, xmax));
}
cout << adj+ans << '\n';
}
}
