[Problem proposal] (Problem title)

[aaron20100919]

Problem name: Bitset Xor Shift
Problem ID: bitset_xor_shift

Problem

You are given a binary string s of length (n). Perform (m) operations on it.

Each operation is described by an integer shift, meaning:

[
s \gets s \ \oplus \ (s \gg \text{shift})
]

After each operation, output the number of 1's in s.

Here, (\oplus) represents bitwise XOR.

• If shift > 0, shift s to the right.
• If shift < 0, shift s to the left.
• If shift = 0, no shifting occurs.

Constraint

• (1 \le n, m \le 10^4)

Input

n m
s
shift_1
shift_2
...
shift_m

• s is a binary string of length n.
• Each shift_i is an integer satisfying (0 \le |\text{shift}_i| < n).

Output

c_1
c_2
...
c_m

• c_i is the number of 1's in s after the (i)-th operation.

Example

Input:

5 3
10101
2
-1
0

Output:

1
0
0

Explanation:

1. 10101 ^ (10101 >> 2) = 10101 ^ 00101 = 10000 → 1's count = 1
2. 10000 ^ (10000 << 1) = 10000 ^ 10000 = 00000 → 1's count = 0
3. 00000 ^ (00000 >> 0) = 00000 → 1's count = 0

[NachiaVivias]

@aaron20100919
To clarify, will you explain the background of this proposal?

• What method is most intended? What is the intended complexity?
• Do you know something such as related tasks outside of Library Checker?

[aaron20100919]

Because the hand-written bitset uses loop unrolling, its constant is smaller than that of std::bitset.