AT_joisp2025_h 会議 (Conference)

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 $ の個数の最小値を求めよ． 会場の情報，また検討すべきシナリオの情報が与えられたとき，質問に回答するプログラムを作成せよ． ---

入力は以下の形式で標準入力から与えられる． > $ N $ $ S $ $ Q $ $ X_1 $ $ Y_1 $ $ Z_1 $ $ X_2 $ $ Y_2 $ $ Z_2 $ $ \vdots $ $ X_Q $ $ Y_Q $ $ Z_Q $

標準出力に $ Q $ 行出力せよ． $ k $ 行目 ( $ 1 \leqq k \leqq Q $ ) には，会場が未定の会議について， $ X_k $ 個に会場 A を， $ Y_k $ 個に会場 B を， $ Z_k $ 個に会場 C を割り当てることにした場合の $ j $ 日目と $ j+1 $ 日目で会議の会場が異なるような $ j $ の個数の最小値を出力せよ．

### 小課題 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 $ 点) 追加の制約はない． --- ### Sample Explanation 1 $ 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 $ の制約を満たす． --- ### Sample Explanation 2 この入力例はすべての小課題の制約を満たす． --- ### Sample Explanation 3 この入力例は小課題 $ 1,2,4,8 $ の制約を満たす． ### Constraints - $ 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 $ )．