Binary Alchemy

Time limit: 2.0 seconds Memory limit: 256 MB

You are given a dynamic binary string S of length N.

The string changes over time through point flips.

For any binary string T, define val(T) as the integer represented by the last min(60, |T|) characters of T, where the rightmost character is the least significant bit.

Also define popcount(x) as the number of set bits in the binary representation of x.

Queries

You must process Q queries of two types.

Type 1 — Flip

1 i

Flip the i-th character of S.

That is:

• 0 becomes 1
• 1 becomes 0

Type 2 — Balanced Partition Optimization

2 l r k

Let:

L = r - l + 1

It is guaranteed that:

1 ≤ k ≤ L

Split S[l..r] into exactly k non-empty contiguous parts:

S[l..r] = P₁ + P₂ + ... + Pₖ

The partition must be balanced, meaning each part has length either:

floor(L / k)

or

ceil(L / k)

For a partition, define:

X = val(P₁) ⊕ val(P₂) ⊕ ... ⊕ val(Pₖ)

Your task is to maximize:

popcount(X)

over all valid balanced partitions.

Input Format

• First line: integers N and Q
• Second line: binary string S
• Next Q lines:

1 i 2 l r k

Output Format

For each query of type 2, output the maximum possible value of popcount(X).

Example

Input

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

Output

3 2 0 1

Explanation

Initial string:

10101

Query: 2 1 5 2

Balanced partitions have lengths 2 and 3.

Possible splits:

10 | 101

2 ⊕ 5 = 7 popcount(7) = 3

and

101 | 01

5 ⊕ 1 = 4 popcount(4) = 1

The maximum is 3.

Query: 1 3

Flip the 3rd character:

10101 -> 10001

Query: 2 1 5 2

The best answer is 2.

Query: 2 2 4 2

The substring is:

000

Any balanced split gives XOR 0, so the answer is 0.

Query: 2 1 3 1

Only one part exists:

100

val(100) = 4 popcount(4) = 1

Constraints

1 ≤ N, Q ≤ 2 · 10^5 S[i] ∈ {0,1} 1 ≤ i ≤ N 1 ≤ l ≤ r ≤ N 1 ≤ k ≤ 10 r - l + 1 ≤ 60 · k

Notes

• val(T) depends only on the last at most 60 bits.
• Since r - l + 1 ≤ 60 · k, every part has length at most 60.