Binary Substring Rearrangement Divisibility

Pupil discovered that for a decimal number, rearranging its digits does not affect whether it is divisible by 3, because divisibility by 3 depends only on the sum of the digits. He now wonders whether a similar property holds in binary.

You are given a binary string S of length n. You have to answer multiple operations. In each query you are given a subinterval [L, R] of the current binary string, and you must count how many different contiguous substrings (distinct by their starting or ending indices) of that subinterval can be rearranged (the permutation may include leading zeros) into a binary number that is divisible by 3.

In addition, there are update operations that change a single character of the string. Note that rearrangement can change the positions arbitrarily. Recall that a binary string (of fixed length L) with exactly k ones can be rearranged arbitrarily. If we view the resulting number in base 2 as \(\sum_{i=0}^{L-1} b_i 2^i\) (with \(b_i\) being the digit in the \(i\)th position, counting from the least significant digit at index 0) then divisibility by 3 depends on the choice of positions of 1’s. Since \(2^i\) modulo 3 cycles as \(2^0\equiv 1,\ 2^1\equiv 2,\ 2^2\equiv 1,\ 2^3\equiv 2,\dots\) the problem reduces to determining if there exists an integer \(r\) (which is the number of ones placed in even positions among the rearranged digits) in the interval \[ \max(0,k-\lfloor L/2\rfloor) \le r \le \min(k, \lceil L/2 \rceil) \] such that \[ 2k - r \equiv 0 \; (\bmod\; 3). \] Equivalently, letting \(r_0\equiv 2k \; (\bmod\; 3)\), the substring is valid if \(k=0\) (which represents the number 0) or if \(k\ge2\) and there exists an integer \(r \in [\max(0,k-\lfloor L/2\rfloor),\min(k,\lceil L/2\rceil)]\) with \(r\equiv r_0\) modulo 3.

Your task is to process both query and update operations. For a query operation, output the count of contiguous substrings in the specified interval [L, R] which satisfy the above condition.

Input format:

n m
S
op1
op2
... 
op_m

Here n is the length of the binary string, m is the number of operations. The string S consists of characters '0' and '1'. Each operation is either a query or an update:

• Query: "Q L R" meaning that you need to answer for the subinterval S[L..R] (1-indexed).
• Update: "C pos ch" meaning change the character at position pos (1-indexed) to ch (where ch is either '0' or '1').

Output format: For each query, output the corresponding count on a new line.

Note: It is guaranteed that the provided test cases are small enough such that a solution with \(O(n^2)\) per query will pass.

inputFormat

The first line contains two integers n and m, where n is the length of the binary string and m is the number of operations.

The second line contains a binary string S of length n.

The next m lines each contain an operation in one of the following formats:

• "Q L R" for a query on the subinterval from L to R (1-indexed).
• "C pos ch" for an update operation changing the character at position pos to ch.

outputFormat

For each query operation, output a single integer representing the number of valid contiguous substrings (by interval) in the specified range that can be rearranged to form a binary number divisible by 3.

sample

5 5
10101
Q 1 5
Q 2 4
C 3 0
Q 1 5
Q 3 3

7
2
7
1

</p>