一条线上有 $$$n$$$ 个灯,编号从 $$$1$$$ 到 $$$n$$$。每个都有一个初始状态关闭($$$0$$$)或打开($$$1$$$)。
给定您 $$$\{1, 2, \dots, n\}$$$ 的 $$$k$$$ 个子集 $$$A_1, \ldots, A_k$$$,使得任意三个子集的交集为空。换句话说,对于所有 $$$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$$$ 之间),它们可以关闭或打开。
您必须为所有 $$$1 \le i \le n$$$ 计算 $$$m_i$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 3 \cdot 10^5$$$)。
第二行包含长度为 $$$n$$$ 的二进制字符串,表示每个灯的初始状态(如果 $$$s_i = 0$$$,则灯 $$$i$$$ 关闭,如果 $$$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$$$ 同时打开所需的最少操作数。
示例
输入 #1
7 3 0011100 3 1 4 6 3 3 4 7 2 2 3
输出 #1
1 2 3 3 3 3 3
输入 #2
8 6 00110011 3 1 3 8 5 1 2 5 6 7 2 6 8 2 3 5 2 4 7 1 2
输出 #2
1 1 1 1 1 1 4 4
输入 #3
5 3 00011 3 1 2 3 1 4 3 3 4 5
输出 #3
1 1 1 1 1
输入#4
19 5 1001001001100000110 2 2 3 2 5 6 2 8 9 5 12 13 14 15 16 1 19
输出#4
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$$$;
- 对于$$$i \ge 3$$$,我们可以对$$$A_1$$$、$$$A_2$$$和$$$A_3$$$进行操作,最终状态将是$$$1111111$$$。
在第二个示例中:
- 对于$$$i \le 6$$$,我们可以只对$$$A_2$$$应用一次操作,最终状态将是$$$11111101$$$;
- 对于$$$i \ge 7$$$,我们可以对$$$A_1,A_3,A_4,A_6$$$进行操作,最终状态将是$$$11111111$$$。