CSES - Bit Inversions | Nghịch đảo bit - LQDOJ: Le Quy Don Online Judge

CSES - Bit Inversions | Nghịch đảo bit

Tác giả:

Dạng bài

Điểm: 1700 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Có một xâu nhị phân gồm $n$ bit. Sau đó, có một số truy vấn đảo ngược một bit bất kì. Sau mỗi thay đổi, bạn cần phải thông báo độ dài của xâu con dài nhất có các bit giống nhau.

Input

Dòng đầu tiên chứa một xâu nhị phân gồm $n$ bit. Các bit được đánh số $1,2,\dots,n$.

Dòng tiếp theo chứa số nguyên $m:$ số lượng thay đổi.

Dòng cuối cùng chứa $m$ số nguyên $x_1, x_2, \dots, x_m$ mô tả các thay đổi.

Output

Sau mỗi thay đổi, in ra độ dài của xâu con dài nhất có các bit của nó giống nhau.

Constraints

$1≤n≤2⋅10^5$
$1≤m≤2⋅10^5$
$ 1≤x_i≤n$

Example

Sample Input:

001011
3
3 2 5

Sample Output:

4 2 3

Note

Xâu nhị phân trước hết trở thành 000011, sau đó là 010011, và cuối cùng là 010001

Bình luận

0
nguyen_ducminh 2:42 a.m. 16 Tháng 9, 2023
CSES - Bit Inversions | Đảo nghịch bit

Cho một xâu nhị phân độ dài $n$. Có một số phép biến đổi, trong đó một phép biến đổi làm đảo nghịch một bit nào đó. Sau mỗi phép biến đổi, nhiệm vụ của bạn là tính độ dài của xâu con dài nhất mà có các bit giống nhau.

Input

Dòng đầu tiên gồm một xâu nhị phân chứa $n$ bit ($1 \leq n \leq 2\times10^5$). Các bit được đánh số theo thứ tự $1,2,...,n$.

Dòng tiếp theo gồm một số nguyên $m$ ($1 \leq m \leq 2\times10^5$) - số lượng phép biến đổi.

Dòng cuối cùng gồm $m$ số nguyên $x_1,x_2,...,x_m$ ($1 \leq x_i \leq n$) mô tả các phép biến đổi.

Output

Sau mỗi phép biến đổi, in ra độ dài của xâu con dài nhất chứa các bit giống nhau.

Test 1

Input

001011 3 3 2 5

Output

4 2 3

Note

Xâu nhị phân biến đổi thành 000011, sau đó là 010011, và cuối cùng là 010001.