D. Decisive Duels
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

David is an enthusiastic badminton player who competes in tournaments regularly. There is just one caveat - he's actually quite bad at badminton and, therefore, frequently loses in the first round. Therefore he asks his friend, Dave, for help. Dave is a master in parallel universes, and after intensive research, he found out that all David's matches can be represented using a long binary string $$$S$$$, whereas each match is a substring of the long string. Each character represents a point, 1 means David wins the point, and a 0 means his opponent wins the point. A match progresses by iterating through the characters of the substring in order until one player wins, and the remainder of the string is discarded. The universe will implode if the whole substring is scanned without producing a winner.

Since David lives in the far future, badminton rules have changed slightly. To win, a player must both

  1. Score at least $$$k$$$ points ($$$k$$$ can differ across different games and is denoted as $$$k_i$$$ for the $$$i$$$-th game)
  2. Score at least two more points than their opponent

Since David is still horrible at badminton, he asks Dave to help using his latest timeline-editing tool. Since the tool is still relatively new, it can only be applied on a copy of the substring and does not persist to the other timelines, so all queries are independent.

David now has $$$Q$$$ queries for you. For each query, given the substring defined by $$$l_i$$$ and $$$r_i$$$ (which is $$$S_{l_i}S_{l_i+1}S_{l_i+2}\dots S_{r_i-1}S_{r_i}$$$) and $$$k_i$$$, what is the minimum number of insertions (adding a character anywhere in the substring) needed such that the universe does not implode and he wins the match?

Input

The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \leq N, Q \leq 10^5$$$), the length of the binary string and the number of queries respectively.

The second line of the input consists of the binary string $$$S$$$ of length $$$N$$$.

The $$$i^{th}$$$ of the remaining $$$Q$$$ lines each contains three integers $$$l_i$$$, $$$r_i$$$, $$$k_i$$$ ($$$1 \leq l_i \leq r_i \leq N$$$, $$$0 \leq k_i \leq 10^5$$$), the index of the leftmost and rightmost character of the substring and minimum points needed to win.

Output

Output $$$Q$$$ lines, one for each query:

The minimum number of insertions needed such that the universe does not implode and David wins the match.

Example
Input
13 3
0110110000100
1 13 7
3 6 3
2 11 7
Output
3
0
2
Note

Let's consider the first query in the example. The queried substring is 0110110000100, with $$$k$$$ being $$$7$$$.

One way to use $$$3$$$ insertions to change the string into 0110110100011100, with the added 1s underlined.

The match progresses as such:

Character scannedCurrent score (David : Opponent)
0$$$0 : 1$$$
1$$$1 : 1$$$
1$$$2 : 1$$$
0$$$2 : 2$$$
1$$$3 : 2$$$
1$$$4 : 2$$$
0$$$4 : 3$$$
1$$$5 : 3$$$
0$$$5 : 4$$$
0$$$5 : 5$$$
0$$$5 : 6$$$
1$$$6 : 6$$$
1$$$7 : 6$$$
1$$$8 : 6$$$

We note that the 00 at the end of the string is not scanned since the match finishes with David winning before that.

It is also possible to show that $$$3$$$ insertions are the minimum number needed to ensure David wins.