CSES 1188 ↗

Bit Inversions

After each bit flip, the length of the longest run of equal bits.

0
submissions
—
best score

There is a bit string consisting of n bits. Then, there are some changes that invert one given bit. Your task is to report, after each change, the length of the longest substring whose each bit is the same.

Input

The first input line has a bit string consisting of n bits. The bits are numbered 1,2,…,n.

The next line contains an integer m: the number of changes.

The last line contains m integers x1,x2,…,xm describing the changes.

Output

After each change, print the length of the longest substring whose each bit is the same.

Constraints

  • 1≤n≤2⋅105
  • 1≤m≤2⋅105
  • 1≤xi≤n

Example

Input:

001011
3
3 2 5

Output:

4 2 3

Explanation: The bit string first becomes 000011, then 010011, and finally 010001.

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/BitInversions/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Results

No scoring submissions yet. One counts once the kernel accepts its proof and every test passes.

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.