AT_utpc2025_m Max Conference

> [Conference](https://www2.ioi-jp.org/camp/2025/2025-sp-tasks/contest3/conference.pdf) を解いた人は、自然にこの問題を思いついているかもしれません。 長さ $ N $ の文字列 $ S $ が与えられます。ここで、 $ S $ の各文字は `A`, `B`, `C`, `?` のいずれかであり、特に $ S $ の $ 1 $ 文字目と $ N $ 文字目は `A` です。 ここで、各文字が `A`, `B`, `C` のいずれかである長さ $ N $ の文字列の**スコア**を、文字列の $ i $ 文字目と $ i+1 $ 文字目が異なるような整数 $ i \ (1 \leq i \leq N-1) $ の個数とします。 $ Q $ 個のクエリに答えてください。 $ i $ 番目のクエリの内容は以下の通りです。 > 非負整数 $ X_i, Y_i, Z_i $ が与えられます。ここで、 $ X_i + Y_i + Z_i $ は $ S $ の `?` の個数に等しいです。 $ S $ の `?` のうち $ X_i $ 個を `A` に、 $ Y_i $ 個を `B` に、 $ Z_i $ 個を `C` に置き換えて得られる文字列のスコアとしてありうる最大の値を出力してください。

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

$ Q $ 行出力せよ。 $ i $ 行目には $ i $ 番目のクエリに対する答えを出力せよ。

### Sample Explanation 1 - $ 1 $ 番目のクエリでは、`ABCBABCBA` と置き換えればスコアを $ 8 $ とできます。 - $ 2 $ 番目のクエリでは、`ABABAACAA` と置き換えればスコアを $ 6 $ とできます。 - $ 3 $ 番目のクエリでは、`ACCBCCCCA` と置き換えればスコアを $ 4 $ とできます。 ### Constraints - $ N, Q, X_i, Y_i, Z_i $ は整数 - $ 2 \leq N \leq 3 \times 10^5 $ - $ S $ は `A`, `B`, `C`, `?` からなる長さ $ N $ の文字列 - $ S $ の $ 1 $ 文字目と $ N $ 文字目は `A` - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 0 \leq X_i $ - $ 0 \leq Y_i $ - $ 0 \leq Z_i $ - $ X_i + Y_i + Z_i $ は $ S $ に含まれる `?` の個数と等しい