题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

使用正整数 $N$ 构造的字符串 $S_N$ 定义如下。这里的 $\lfloor N/2 \rfloor$ 表示 $N$ 除以 2 的向下取整值。

1. 当 $N = 1$ 时：$S_N = 1$（即由一个字符 '1' 组成的字符串）。
2. 当 $N \geq 2$ 且 $N$ 是偶数时：$S_N = S_{\lfloor N/2 \rfloor} 0 S_{\lfloor N/2 \rfloor}$（即用一个字符 '0' 夹在两个 $S_{\lfloor N/2 \rfloor}$ 之间）。
3. 当 $N \geq 2$ 且 $N$ 是奇数时：$S_N = S_{\lfloor N/2 \rfloor} 1 S_{\lfloor N/2 \rfloor}$（即用一个字符 '1' 夹在两个 $S_{\lfloor N/2 \rfloor}$ 之间）。

根据上述定义，我们可以如下计算 $S_{13}$：

• 由于 $N = 13$ 是奇数，适用第 3 条规则，因此 $S_{13} = S_6 1 S_6$。
• 又由于 $S_6$ 是偶数，适用第 2 条规则，因此 $S_6 = S_3 0 S_3$，所以 $S_{13} = S_3 0 S_3 1 S_3 0 S_3$。
• 而 $S_3$ 是奇数，进一步展开得到 $S_3 = S_1 1 S_1$，而 $S_1 = 1$，所以 $S_3 = 1 1 1$。

因此，$S_{13} = 111011111110111$。

给定正整数 $N$，你需要编写程序处理 $Q$ 个查询。

第 $q$ 个查询（$1 \leq q \leq Q$）给出三个整数 $(i_q, j_q, k_q)$，要求回答：在 $S_N[i_q..j_q]$ 区间中，最多包含 $k_q$ 个 '0' 的最长子字符串的长度是多少？

例如：

• 查询 $(1, 15, 0)$ 询问的是整个 $S_{13}$ 中只包含 '1' 的最长子串，其长度为 7。
• 查询 $(2, 14, 2)$ 涉及子串 $S_{13}[2..14] = 1101111111011$，其中恰好有两个 '0'，因此整个子串就是答案，长度为 13。

部分字符串的定义如下：

• 给定一个长度为 $l$ 的字符串 $s$ 和两个满足 $1 \leq i \leq j \leq l$ 的整数 $i$ 和 $j$，$s[i..j]$ 表示从第 $i$ 个字符开始到第 $j$ 个字符为止的所有字符所组成的字符串。
• 例如：若 $s = 0100101$，则 $s[3..5] = 001$，$s[4..7] = 0101$，而 $1010$ 不是其子串。

输入格式

第一行包含两个整数 $N$ 和 $Q$，用一个空格隔开。

接下来的 $Q$ 行，每行三个整数 $i_q$、$j_q$、$k_q$，表示第 $q$ 个查询。

输出格式

对每个查询，输出一行，仅包含一个整数，即最长子字符串的长度。

13 3
1 15 0
2 14 2
2 8 0

7
13
4

提示

约束条件

• $1 \leq N \leq 10^{18}$
• $1 \leq Q \leq 10\,000$
• 所有查询中 $k_q$ 的总和不超过 $10\,000$，即 $\sum_{q=1}^{Q} k_q \leq 10\,000$
• 对所有 $q$ 满足 $1 \leq i_q \leq j_q \leq |S_N|$（其中 $|S_N|$ 是字符串 $S_N$ 的长度）

子任务

1. （5 分）$N = 2^t$，其中 $t$ 为非负整数，即 $N$ 是 $1, 2, 4, 8, \ldots$ 等 2 的幂
2. （11 分）$N \leq 1\,000$
3. （17 分）所有查询中子串长度之和不超过 $100\,000$，即 $\sum_{q=1}^{Q}(j_q - i_q + 1) \leq 100\,000$
4. （25 分）所有查询中 $k_q = 0$
5. （42 分）无额外约束条件