Bật đèn theo tiền tố

Có $n$ bóng đèn xếp thành một hàng, đánh số từ $1$ đến $n$. Mỗi bóng đèn ban đầu ở trạng thái tắt ($0$) hoặc bật ($1$).

Cho $k$ tập con $A_1,A_2,\dots ,A_k$ của $\{1,2,\dots ,n\}$, thỏa mãn điều kiện: giao của ba tập con bất kỳ luôn rỗng. Nói cách khác, với mọi $1\le i_1<i_2<i_3\le k$ thì $A_{i_1}\cap A_{i_2}\cap A_{i_3}=\varnothing$ (tức là mỗi bóng đèn thuộc nhiều nhất hai tập con).

Trong một thao tác, bạn chọn một tập con $A_j$ và đảo trạng thái của tất cả các bóng đèn thuộc $A_j$ (đèn đang bật thành tắt và ngược lại).

Dữ liệu đảm bảo rằng với các tập con đã cho, luôn có thể thực hiện một số thao tác để bật đồng thời tất cả các bóng đèn.

Gọi $m_i$ là số thao tác ít nhất cần thực hiện để $i$ bóng đèn đầu tiên đồng thời được bật. Lưu ý rằng không có ràng buộc nào về trạng thái của các bóng đèn còn lại (từ $i+1$ đến $n$), chúng có thể bật hoặc tắt tùy ý.

Hãy tính $m_i$ với mọi $1\le i\le n$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$.
• Dòng thứ hai chứa một xâu nhị phân độ dài $n$ mô tả trạng thái ban đầu của các bóng đèn (bóng $i$ tắt nếu ký tự thứ $i$ là $0$, bật nếu là $1$).
• Tiếp theo là mô tả của $k$ tập con. Mô tả của mỗi tập con gồm:
  • Một dòng chứa số nguyên $c$ ($1\le c\le n$) là số phần tử của tập con.
  • Một dòng chứa $c$ số nguyên phân biệt $x_1,\dots ,x_c$ ($1\le x_i\le n$) là các phần tử của tập con.

Dữ liệu ra

In ra $n$ dòng, dòng thứ $i$ chứa một số nguyên $m_i$: số thao tác ít nhất để bật đồng thời các bóng đèn từ $1$ đến $i$.

Ràng buộc

• $1\le n,k\le 3·{10}^5$
• Giao của ba tập con bất kỳ luôn rỗng.
• Luôn tồn tại cách bật đồng thời toàn bộ các bóng đèn.

Ví dụ