問題文

0 と 1 のみで作られた長さ $N$ の文字列 $S$ が与えられます。

$Q$ 個のクエリが与えられます。$i$ 個目のクエリは以下のようなものです。

$S$ の左から $L_i$ 個目を左端、左から $R_i$ 個目を右端として取り出した連続部分文字列 $X$ に対し、以下の操作を $0$ 回以上出来ます。一連の操作後の文字列 $X$ の長さの最小値を求めてください。

• $K_i$ 個 0 が連続している部分を $K_i-1$ 個の 1 に置き換えるか、$K_i$ 個 1 が連続している部分を $K_i-1$ 個の 0 に置き換える。

入力

$N\ \ Q$
$S$
$L_1\ \ R_1\ \ K_1$
$L_2\ \ R_2\ \ K_2$
$:$
$L_Q\ \ R_Q\ \ K_Q$

• $2 \leq N \leq 2×10^5$
• $1 \leq Q \leq 2×10^5$
• $1 \leq L_i < R_i \leq N$
• $2 \leq K_i \leq R_i - L_i + 1$
• $S$ は0 と 1 からなる長さ $N$ の文字列である
• 入力される数値は整数である

出力

$i \ (1 \leq i \leq Q)$ 行目に $i$ 個目のクエリの答えを出力し、最後に改行せよ。

サンプル

7 3
0100010
3 5 2
1 5 3
1 7 2

2
2
2