AT_pakencamp_2025_day3_o Giraffe? Zebra?

整数 $ G $ と、`0` と `1` からなる文字列 $ S $ が与えられます。 ある`0` と `1` からなる空でない文字列が、 - **キリン文字列**であるとは、長さが $ G $ 以上であることを指します。 - **シマウマ文字列**であるとは、同じ文字が隣り合っている部分が存在しないことを指します（長さ $ 1 $ の文字列はシマウマ文字列です）。 - **オカピ文字列**であるとは、キリン文字列でもシマウマ文字列でもないことを指します。 $ Q $ 個のクエリを処理してください。 $ i $ 番目のクエリでは、整数 $ L_i,R_i,T_i $ が与えられるので、以下のクエリに答えてください。 - $ S $ の $ L_i $ 文字目から $ R_i $ 文字目を取り出した文字列の中に含まれる部分文字列のうち、 - $ T_i=1 $ のとき、キリン文字列の数を答えよ。 - $ T_i=2 $ のとき、シマウマ文字列の数を答えよ。 - $ T_i=3 $ のとき、オカピ文字列の数を答えよ。 ただし、同じ文字列でも取り出す場所が違えば異なる部分文字列として扱います。

入力は以下の形式で標準入力から与えられる。 > $ G $ $ S $ $ Q $ $ L_1 $ $ R_1 $ $ T_1 $ $ L_2 $ $ R_2 $ $ T_2 $ $ \vdots $ $ L_Q $ $ R_Q $ $ T_Q $

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

### Universal Cup参加者へ この問題は Universal Cup に収録される際に削除されます。そのため、Universal Cup に AtCoder での結果を使用する場合はこの問題以外を先に解くことをおすすめします。 ### 小課題 1. ( $ 10 $ 点) $ T_i=1 $ 2. ( $ 50 $ 点) $ T_i=2 $ 3. ( $ 40 $ 点) 追加の制約はない。 ### Constraints - $ 1\leq G\leq |S| $ - $ 1\leq |S| \leq 2\times 10^5 $ - $ S $ は `0` と `1` からなる - $ 1\leq Q\leq 2\times 10^5 $ - $ 1\leq L_i\leq R_i\leq N $ - $ 1\leq T_i\leq 3 $ - $ G,Q,L_i,R_i,T_i $ は整数