K 理事長は N 日間の会議を運営する予定である． 1 日に会議は 1 つ開催され，メインの会場 A とサブの会場 B, C のいずれか 1 つが使用される．

各会議の会場に関する情報は A, B, C, ? からなる文字列 S で与えられる． i 日目 (1\leqq i \leqq N) の会議の会場は，S の i 文字目が A の場合は会場 A，B の場合は会場 B，C の場合は会場 C，? の場合は未定である．ただし， 1 日目と N 日目の会議は多くの人が参加するため，会場 A が使われることが決まっている．

これから K 理事長は，会場が未定の会議について，それぞれ会場 A, B, C のいずれか 1 つを割り当てようとしている． また，移動の負担を減らすために，j 日目と j+1 日目で会議の会場が異なるような j (1\leqq j \leqq N-1) の個数を最小にしたいと考えている．

会場が未定の会議の割り当てについて，Q 個のシナリオを検討し，上記の個数の最小化を考えたい． k 番目 (1 \leqq k \leqq Q) のシナリオとそれに対応する質問は以下の通りである．

• 会場が未定の会議について，X_k 個に会場 A を，Y_k 個に会場 B を，Z_k 個に会場 C を割り当てることにする．この時，j 日目と j+1 日目で会議の会場が異なるような j の個数の最小値を求めよ．

会場の情報，また検討すべきシナリオの情報が与えられたとき，質問に回答するプログラムを作成せよ．

制約

• 2 \leqq N \leqq 300\,000．
• S は A, B, C, ? からなる長さ N の文字列である．
• S の 1 文字目と N 文字目 は A である．
• 1 \leqq Q \leqq 200\,000．
• 0 \leqq X_k (1\leqq k \leqq Q)．
• 0 \leqq Y_k (1\leqq k \leqq Q)．
• 0 \leqq Z_k (1\leqq k \leqq Q)．
• X_k + Y_k + Z_k は S に含まれる ? の個数と等しい (1\leqq k \leqq Q)．
• N, Q, X_k, Y_k, Z_kは整数である (1\leqq k \leqq Q)．

小課題

1. (4 点) N \leqq 50，S に含まれる ? の個数は 13 以下．
2. (7 点) N \leqq 500．
3. (13 点) N \leqq 5\,000，Q \leqq 10．
4. (18 点) N \leqq 5\,000．
5. (12 点) Q \leqq 10．
6. (8 点) S に C は含まれない，Z_k = 0 (1\leqq k \leqq Q)．
7. (13 点) Z_k = 0 (1\leqq k \leqq Q)．
8. (25 点) 追加の制約はない．

入力例 1

9
A??B??C?A
3
1 3 1
4 1 0
0 0 5

出力例 1

3
4
4

1 番目のシナリオでは，会場が未定の会議 5 個のうち， 1 個に会場 A を， 3 個に会場 B を， 1 個に会場 C を割り当てる． 例えば，各会議の会場に関する情報が ABBBBCCAA となるような割り当て方が考えられる．この場合， j 日目と j+1 日目で会議の会場が異なるような j は 1,5,7 の 3 個となる． j の個数を 2 個以下にするような方法は存在しないため， 1 行目には 3 を出力する．

2 番目のシナリオでは，会場が未定の会議 5 個のうち， 4 個に会場 A を， 1 個に会場 B を割り当てる． 例えば，各会議の会場に関する情報が AAABBACAA となるような割り当て方が考えられる．この場合，j 日目と j+1 日目で会議の会場が異なるような j は 3,5,6,7 の 4 個となる． j の個数を 3 個以下にするような方法は存在しないため， 2 行目には 4 を出力する．

3 番目のシナリオでは，会場が未定の会議 5 個のうち， すべてに会場 C を割り当てる． j 日目と j+1 日目で会議の会場が異なるような j は 1,3,4,8 の 4 個となり， 3 行目には 4 を出力する．

この入力例は小課題 1,2,3,4,5,8 の制約を満たす．

入力例 2

12
A???A?B????A
4
0 8 0
2 6 0
7 1 0
3 5 0

出力例 2

4
4
2
2

この入力例はすべての小課題の制約を満たす．

入力例 3

28
ACB??B???BCB??B????B?AAA?BBA
26
6 1 6
4 5 4
2 3 8
9 2 2
11 0 2
8 4 1
11 0 2
2 0 11
0 1 12
12 1 0
10 3 0
1 4 8
3 7 3
2 8 3
1 3 9
11 1 1
7 0 6
6 4 3
8 4 1
0 10 3
13 0 0
11 1 1
0 6 7
2 8 3
9 0 4
0 0 13

出力例 3

15
11
13
13
15
12
15
15
16
15
13
12
10
9
13
15
15
11
12
9
15
15
11
9
15
17

この入力例は小課題 1,2,4,8 の制約を満たす．