时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的 01 串 $s$。你可以进行若干次操作，每次选择一个字符将其翻转（即 0 变为 1，1 变为 0）。

对于一个非负整数 $k$，设所有满足以下条件的字符串中，字典序最小的一个字符串为 $t_k$：

• $t_k$ 可以由 $s$ 经过最多 $k$ 次上述操作得到。
• $t_k$ 中不存在相邻的两个字符 1。

若无论如何操作都无法得到满足条件的字符串，则认为 $t_k$ 不存在。

现在有 $Q$ 次询问，每次给出三个整数 $k, l, r$。若 $t_k$ 不存在，请输出 -1；否则请输出子串 $t_k[l \dots r]$ 中 1 的个数。

格式

输入格式

第一行包含两个正整数 $n$ 和 $Q$。

第二行包含一个长度为 $n$ 的 01 串 $s$。

接下来 $Q$ 行，每行包含三个整数 $k_i, l_i, r_i$，表示一次询问。

输出格式

输出共 $Q$ 行，每行一个整数，依次表示每次询问的答案。

样例

样例输入 #1

6 4
111011
1 1 6
2 1 6
3 1 6
3 2 5

样例输出 #1

-1
3
2
1

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$1 \le n, Q \le 2 \times 10^5$，$s$ 是长度为 $n$ 的 01 串，$0 \le k_i \le n$，$1 \le l_i \le r_i \le n$。