现在已经是 3202 年了，你还在解决传统的区间查询问题吗？

Little Cyan Fish 是区间查询问题的头号粉丝，他想在 3202 年找到最好的区间查询任务。幸运的是，他发现了一个关于二进制字符串的问题。他非常喜欢二进制字符串，因为它们在 2202 年引出了“最好的问题”（Best Problem）。

对于一个长度为 $n$ 的二进制字符串 $s = s_1s_2 \dots s_n$，记 $L(s)$ 为所有满足 $i=1$ 或 $s_i \neq s_{i-1}$ 的下标 $i$ ($1 \le i \le n$) 构成的集合。例如，$L(0011100) = \{1, 3, 6\}$，$L(00101101) = \{1, 3, 4, 5, 7, 8\}$，以及 $L(000) = \{1\}$。特别地，如果 $s = \varepsilon$ 是空字符串，则 $L(\varepsilon) = \emptyset$（空集）。

令 $f(s)$ 为从 $s$ 中删除所有下标在 $L(s)$ 中的字符后得到的字符串。下表展示了函数 $f$ 的几个示例：

Little Cyan Fish 发现的问题要求他确定字符串 $f^k(s)$ 的长度，其中 $f^k(s)$ 定义如下：

$$f^k(s) = \begin{cases} f^{k-1}(f(s)) & k \ge 1 \\ s & k = 0 \end{cases}$$

Little Cyan Fish 想用它创建一个区间查询问题。因此，他给你一个字符串 $s = s_1s_2 \dots s_n$ 和 $q$ 次查询。在每次查询中，给定三个整数 $l, r$ 和 $k$。你的任务是输出字符串 $f^k(s[l \dots r])$ 的长度，其中 $s[l \dots r]$ 表示 $s_l s_{l+1} \dots s_r$。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 5 \times 10^5$)，分别表示字符串 $s$ 的长度和 Little Cyan Fish 想要执行的查询次数。

下一行包含一个二进制字符串 $s$ ($|s| = n, s_i \in \{0, 1\}$)。

接下来的 $q$ 行描述查询。第 $i$ 行包含三个整数 $l, r, k$ ($1 \le l \le r \le n, 0 \le k \le n$)。

输出格式

对于每次查询，输出一行，包含一个整数，表示 $f^k(s[l \dots r])$ 的长度。

样例

输入 1

9 7
100110001
2 5 1
3 6 1
4 8 2
2 7 1
1 9 1
1 9 0
1 9 8

输出 1

2
1
1
3
4
9
0

说明

在第一次查询中，$s[2 \dots 5] = 0011$，且 $f(0011) = 01$。因此答案为 2。

在第二次查询中，$s[3 \dots 6] = 0110$，且 $f(0110) = 1$。因此答案为 1。

在第三次查询中，$s[4 \dots 8] = 11000$，且 $f^2(11000) = f(100) = 0$。因此答案为 1。

在第四次查询中，$s[2 \dots 7] = 001100$，且 $f(001100) = 010$。因此答案为 3。

在第五次查询中，$s[1 \dots 9] = 100110001$，且 $f(100110001) = 0100$。因此答案为 4。

在第六次查询中，$s[1 \dots 9] = 100110001$，且 $f^0(100110001) = 100110001$。因此答案为 9。

在第七次查询中，$s[1 \dots 9] = 100110001$，且 $f^8(100110001) = f^7(0100) = f^6(0) = f^5(\varepsilon) = \varepsilon$。因此答案为 0。