#215950. [JOI Final 2026] 传奇团子吃家 / Legendary Dango Eater

Bitaro 买了一长串团子作为零食。这串团子可以用 个正整数 表示如下。对于每个满足 的整数 ，令 。特别地，我们定义 。

• 这串团子由 个团子组成，从上到下排成一列。
• 每个团子要么是甜的，要么是辣的。每个团子的口味可以描述如下。
  • 如果 是一个满足 的奇数，那么从上往下数第 个到第 个团子是甜的。
  • 如果 是一个满足 的偶数，那么从上往下数第 个到第 个团子是辣的。

在吃这串团子时，Bitaro 制订了 种可能的计划。第 个计划（）由满足 的整数 和 表示，在这个计划中，他吃掉从上往下数第 个到第 个团子。

此外，在吃这串团子时，Bitaro 决定按照以下方式将其分成几口来吃。这里， 是一个正整数，代表 Bitaro 对甜度的偏好。

• 他从上到下吃团子，并且每个团子恰好被吃一次。
• 在一口中，他可以吃掉串上任意正数个连续的团子。如果在那一口吃掉的团子中，甜团子的数量减去辣团子的数量至少为 ，那么 Bitaro 就会感到满足。

给定关于这串团子和计划的信息，编写一个程序，对于每个计划，计算 Bitaro 能够感到满足的最大可能次数。

从标准输入读取以下数据。

向标准输出写入 行。在第 行（），输出在第 个计划中 Bitaro 能够感到满足的最大次数。

样例输入 1

5 2 1
2 1 2 4 3
1 5
2 4

样例输出 1

7
2

样例输入 2

5 2 3
2 1 2 4 3
1 5
2 4

样例输出 2

2
0

样例输入 3

9 4 50
24 26 89 45 84 72 15 31 66
1 9
2 8
4 6
5 6

样例输出 3

3
2
1
1

样例 1

对于第一个计划，Bitaro 吃掉从上往下数第 到第 个团子。通过反复从顶部每口恰好吃一个团子，Bitaro 可以感到满足 次。因为不可能让他感到满足 次或更多，所以你应该输出 。

对于第二个计划，Bitaro 吃掉从上往下数第 到第 个团子。通过反复从顶部每口恰好吃一个团子，Bitaro 可以感到满足 次。因为不可能让他感到满足 次或更多，所以你应该输出 。

这个样例输入满足所有子任务的约束条件。

样例 2

这与样例输入 仅在 的值上有所不同。 对于第一个计划，Bitaro 可以通过分以下四口吃团子来感到满足 次。

• 第一口，他吃掉从上往下数第 到第 个团子。由于甜团子的数量为 ，辣团子的数量为 ，Bitaro 感到满足。
• 第二口，他只吃掉从上往下数第 个团子。由于甜团子的数量为 ，辣团子的数量为 ，Bitaro 没有感到满足。
• 第三口，他吃掉从上往下数第 到第 个团子。由于甜团子的数量为 ，辣团子的数量为 ，Bitaro 没有感到满足。
• 第四口，他吃掉从上往下数第 到第 个团子。由于甜团子的数量为 ，辣团子的数量为 ，Bitaro 感到满足。

因为不可能让他感到满足 次或更多，所以你应该输出 。 对于第二个计划，Bitaro 不可能以让他至少感到满足一次的方式吃团子，所以你应该输出 。

这个样例输入满足子任务 的约束条件。

样例 3

这个样例输入满足子任务 的约束条件。

约束条件

• 。
• 。
• 。
• ()。
• ()。
• 给定的值都是整数。

子任务

1. (6 分) 。
2. (5 分) 。
3. (18 分) 。
4. (27 分) 。
5. (17 分) , 。
6. (27 分) 无附加限制。