Có \(n\) bóng đèn trên một đường thẳng, được đánh số từ \(1\) đến \(n\). Mỗi bóng đèn có trạng thái ban đầu là tắt \((0)\) hoặc mở \((1)\).

Bạn đã cho \(k\) tập con \(A_1, \ldots, A_k\) là tập con của tập \(\{1, 2, \ldots, n\}\), sao cho giao của ba tập hợp con bất kỳ là trống. Nói cách khác, với mọi \(1 \leq i_1 < i_2 < i_3 \leq k\) thì \(A_{i_1} \cap A_{i_2} \cap A_{i_3} = \emptyset\).

Trong một thao tác, bạn có thể chọn một trong số \(k\) tập hợp con và chuyển đổi trạng thái của tất cả các đèn trong đó. Đảm bảo rằng, với các tập hợp con đã cho, có thể làm cho tất cả các bóng đèn được bật đồng thời bằng các hoạt động này.

Gọi \(m_i\) là số thao tác tối thiểu bạn phải làm để \(i\) đèn đầu tiên được bật đồng thời. Lưu ý rằng không có điều kiện đối với trạng thái của các đèn khác (từ \(i + 1\) đến \(n\)), chúng có thể tắt hoặc mở.

Bạn phải tính toán \(m_i\) cho tất cả \(1 \leq i \leq n\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \leq n, k \leq 3 \cdot 10^5\)).
• Dòng thứ hai chứa một chuỗi nhị phân có độ dài \(n\), đại diện cho trạng thái ban đầu của mỗi đèn (đèn \(i\) tắt nếu \(s_i=0\), ngược lại nếu \(s_i=1\)).
• \(k\) nhóm dòng tiếp theo, mỗi nhóm dòng mô tả một tập hợp con theo, ở định dạng sau:
  • Dòng đầu tiên của mô tả chứa một số nguyên \(c\) (\(1 \leq c \leq n\)) - số phần tử trong tập hợp con.
  • Dòng thứ hai của mô tả chứa \(c\) các số nguyên riêng biệt \(x_1, \ldots, x_c\) (\(1 \leq x_i \leq n\)) - các phần tử của tập hợp con.
• Dữ liệu được đảm bảo rằng:
  • Giao của ba tập hợp con bất kỳ là trống.
  • Có thể làm cho tất cả các đèn hoạt động đồng thời bằng một số hoạt động.

Output

• Bạn phải xuất \(n\) dòng. Dòng thứ \(i\) phải chứa một số nguyên duy nhất \(m_i\) - số lượng thao tác tối thiểu cần thiết để các bóng đèn từ \(1\) đến \(i\) được bật đồng thời.

Example

7 3
0011100
3
1 4 6
3
3 4 7
2
2 3

1
2
3
3
3
3
3

8 6
00110011
3
1 3 8
5
1 2 5 6 7
2
6 8
2
3 5
2
4 7
1
2

1
1
1
1
1
1
4
4

5 3
00011
3
1 2 3
1
4
3
3 4 5

1
1
1
1
1

19 5
1001001001100000110
2
2 3
2
5 6
2
8 9
5
12 13 14 15 16
1
19

0
1
1
1
2
2
2
3
3
3
3
4
4
4
4
4
4
4
5

Scoring

• Subtask 1 (\(40\%\) số điểm): \(1 \leq n, k \leq 20\)
• Subtask 2 (\(30\%\) số điểm): \(c = 2\)
• Subtask 3 (\(20\%\) số điểm): \(1 \leq n, k \leq 5000\)
• Subtask 4 (\(10\%\) số điểm): Giới hạn gốc

Nguồn: Bài 3 ngày 1 đề chọn ĐT HSG QG TP.ĐN 2022-2023