CF2244E.Masha and the Garland

Masha has a New Year garland consisting of $n$ bulbs. Each bulb can be either off or on. The state of the garland is given by a binary string $s$ of length $n$, where '0' denotes an off bulb and '1' denotes an on bulb.

Masha considers the garland beautiful if the states of adjacent bulbs strictly alternate. That is, there are no two adjacent bulbs that are both on or both off. For example, the garlands '01010' and '1010' are beautiful, while '0110' and '000' are not.

Yura can apply the following operation to the garland: choose a subsegment and flip the state of all bulbs in it, that is, turn all on bulbs off and all off bulbs on.

Masha invites him to play the following game $q$ times: she chooses a segment from the $l$-th to the $r$-th bulb inclusive, and Yura must make this segment beautiful using at most $k$ operations.

However, Yura is not sure whether this is always possible, so he asks you to determine for each game whether he can make the chosen segment beautiful using no more than $k$ operations. Note that the games are independent, and the garland itself is not actually modified.

玛莎有一串新年彩灯，包含 $n$ 个灯泡。每个灯泡的状态为“关”或“开”。彩灯的状态由一个长度为 $n$ 的二进制字符串 $s$ 表示，其中字符 '0' 表示灯泡关闭，字符 '1' 表示灯泡开启。

玛莎认为一串彩灯是“优美的”，当且仅当相邻灯泡的状态严格交替——即不存在两个相邻灯泡同时为开或同时为关。例如，字符串 '01010' 和 '1010' 是优美的，而 '0110' 和 '000' 不是优美的。

尤拉可以对彩灯执行如下操作：选择一个连续子段，并翻转该子段内所有灯泡的状态（即把所有开启的灯泡关闭，所有关闭的灯泡开启）。

玛莎邀请尤拉进行 $q$ 轮游戏：每轮中，她选定从第 $l$ 个到第 $r$ 个灯泡（含端点）构成的子段，尤拉必须使用至多 $k$ 次操作，使该子段变为优美的。

然而，尤拉不确定是否总能实现目标，因此他请你判断：对每一轮游戏，是否存在一种方案，在不超过 $k$ 次操作的前提下，使所选子段变为优美。注意：各轮游戏相互独立，彩灯本身不会被实际修改。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$) — the length of the garland and the number of games.

The second line contains a binary string $s$ of length $n$, consisting only of characters '0' and '1'.

The next $q$ lines each contain three integers $l$, $r$, and $k$ ($1 \le l \le r \le n$, $0 \le k \le n$) — the boundaries of the segment and the maximum allowed number of operations.

It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases do not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2 \cdot 10^5$）—— 彩灯串的长度和游戏次数。

第二行包含一个长度为 $n$ 的二进制字符串 $s$，仅由字符 '0' 和 '1' 组成。

接下来的 $q$ 行，每行包含三个整数 $l$、$r$ 和 $k$（$1 \le l \le r \le n$，$0 \le k \le n$）—— 区间边界及允许执行操作的最大次数。

保证所有测试用例中 $n$ 的总和与 $q$ 的总和均不超过 $2 \cdot 10^5$。

For each game, output "YES" if the segment can be made beautiful using at most $k$ operations, and "NO" otherwise.

对于每局游戏，如果最多使用 $k$ 次操作即可使该线段变得优美，则输出 "YES"；否则输出 "NO"。

null