C. Освещение префиксов
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В линию было расположено $$$n$$$ ламп, пронумерованных целыми числами от $$$1$$$ до $$$n$$$. Каждая лампа изначально либо выключена ($$$0$$$) или включена ($$$1$$$).

Вам дано $$$k$$$ подмножеств $$$A_1, \ldots, A_k$$$ множества ламп $$$\{1, 2, \dots, n\}$$$, таких что пересечение любых трех подмножеств пусто. Другими словами, для всех $$$1 \le i_1 < i_2 < i_3 \le k$$$ выполнено $$$A_{i_1} \cap A_{i_2} \cap A_{i_3} = \varnothing$$$.

За одну операцию вы можете выбрать одно из этих $$$k$$$ подмножеств и изменить состояние всех ламп из этого подмножества (выключенные лампы становятся включенными, включенные становятся выключенными). Гарантируется, что для данных подмножеств можно совершить несколько операций так, чтобы все лампы стали включенными.

Обозначим за $$$m_i$$$ минимальное количество операций, которое вы должны совершить, чтобы первые $$$i$$$ ламп оказались включенными. Обратите внимание, что при этом состояние других ламп (с номерами между $$$i+1$$$ и $$$n$$$) может быть любым.

Посчитайте $$$m_i$$$ для всех $$$1 \le i \le n$$$.

Входные данные

В первой строке находится два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n, k \le 3 \cdot 10^5$$$).

Во второй строке находится двоичная строка длины $$$n$$$, обозначающая начальное состояние каждой лампы (лампа $$$i$$$ выключена, если $$$s_i = 0$$$, включена, если $$$s_i = 1$$$).

Описание каждого из $$$k$$$ подмножеств следует, в следующем формате:

В первой строке описания находится единственное целое число $$$c$$$ ($$$1 \le c \le n$$$)  — количество элементов в подмножестве.

Во второй строке описания находится $$$c$$$ различных целых чисел $$$x_1, \ldots, x_c$$$ ($$$1 \le x_i \le n$$$)  — элементы подмножества.

Гарантируется, что:

  • Пересечение любых трех подмножеств пусто;
  • С помощью нескольких операций можно сделать все лампы одновременно включенными.
Выходные данные

Вы должны вывести $$$n$$$ строк. В $$$i$$$-й строке должно содержаться единственное целое число $$$m_i$$$  — минимальное количество операций, необходимое для того чтобы сделать все лампы с номерами от $$$1$$$ до $$$i$$$ включенными.

Примеры
Входные данные
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
Примечание

В первом тесте:

  • Для $$$i = 1$$$, мы можем сделать одну операцию с множеством $$$A_1$$$, итоговые состояния будут $$$1010110$$$;
  • Для $$$i = 2$$$, мы можем сделать операции с множествами $$$A_1$$$ и $$$A_3$$$, итоговые состояния будут $$$1100110$$$;
  • For $$$i \ge 3$$$, we can apply operations on $$$A_1$$$, $$$A_2$$$ and $$$A_3$$$, the final states will be $$$1111111$$$.

Во втором тесте:

  • Для $$$i \le 6$$$, мы можем просто сделать одну операцию с множеством $$$A_2$$$, итоговые состояния будут $$$11111101$$$;
  • Для $$$i \ge 7$$$, мы можем сделать операции с множествами $$$A_1, A_3, A_4, A_6$$$, итоговые состояния будут $$$11111111$$$.