Universal Cup参加者へ

この問題は Universal Cup に収録される際に削除されます。そのため、Universal Cup に AtCoder での結果を使用する場合はこの問題以外を先に解くことをおすすめします。

問題文

整数 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 のとき、オカピ文字列の数を答えよ。

ただし、同じ文字列でも取り出す場所が違えば異なる部分文字列として扱います。

制約

• 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 は整数

小課題

1. (10 点) T_i=1
2. (50 点) T_i=2
3. (40 点) 追加の制約はない。

入力例 1

3
010010
3
1 6 1
1 6 2
1 6 3

出力例 1

10
12
1