Problem Statement

You are given a string $S$ of length $N$ consisting only of 0 and 1.

You are given $Q$ queries. The $i$-th query is as follows.

Let $X$ be the substring of $S$ whose left end is the $L_i$-th character from the left and whose right end is the $R_i$-th character from the left. You may perform the following operation on it $0$ or more times. Find the minimum possible length of the string $X$ after the sequence of operations.

• Replace a part consisting of $K_i$ consecutive 0s with $K_i-1$ 1s, or replace a part consisting of $K_i$ consecutive 1s with $K_i-1$ 0s.

Input

$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$ is a string of length $N$ consisting of 0 and 1
• All numbers in the input are integers

Output

On line $i \ (1 \leq i \leq Q)$, output the answer to the $i$-th query, and print a newline at the end.

Sample

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

2
2
2