分数: 266 分
问题陈述
Takahashi 是一家公司的系统管理员。公司拥有 N 类型的资源,每个资源都有一组访问它所需的权限。权限包括 L 权限项,以及需要的权限 i-th 资源由位串表示 S_i 长度 L。位串是由以下组成的串 0 和 1,其中最左边的位是最高有效位 (MSB)。当 p第位(1 \leq p \leq L,将最左边的位算为第 1 位)的位串为
访问该资源需要 1,这意味着 p-th 权限项。
授予员工的访问权限也由位串表示 K 长度 L。员工访问资源的条件 i 是员工拥有该资源所需的所有权限项。换句话说,对于每个位位置,如果 S_i is 1,则位于相同位置的位 K 还必须是 1 (即按位 AND 满足 K \mathbin{\&} S_i = S_i).
Aoki 是公司的安全官,提倡不授予不必要的广泛权限的政策。青木给了高桥 Q 请求。在 j第一个请求 (1 \leq j \leq Q),数量 指定某个员工需要访问的 M_j 资源: c_{j,1}, c_{j,2}, \ldots, c_{j,M_j} (同一请求中资源编号可能重复)。所有权限位串中 K 允许访问所有指定的资源,找到当位串被解释为二进制数时其值最小的一个。
请注意,允许访问所有指定资源的权限位串始终存在(例如,所有位都设置为 1 满足条件)。
约束
- 1 \leq N \leq 10^5
- 1 \leq L \leq 64
- 1 \leq Q \leq 10^5
- S_i 是一个长度为 L 组成
0和1(1 \leq i \leq N) - M_j 是指定的资源数量 j第一个请求,以及 1 \leq M_j \leq N (1 \leq j \leq Q)
- c_{j,k} 是在 j第一个请求,以及 1 \leq c_{j,k} \leq N (1 \leq j \leq Q, 1 \leq k \leq M_j)
- 同一请求中的资源编号可能重复
- \sum_{j=1}^{Q} M_j \leq 10^5
- S_i 作为字符串给出;所有其他输入均为整数
输入
N L Q
S_1
S_2
\vdots
S_N
M_1 c_{1,1} c_{1,2} \ldots c_{1,M_1}
M_2 c_{2,1} c_{2,2} \ldots c_{2,M_2}
\vdots
M_Q c_{Q,1} c_{Q,2} \ldots c_{Q,M_Q}
- 第一行包含三个空格分隔的整数: N 代表资源类型的数量, L 表示位串的长度,以及 Q 代表请求数。
- 第 2 行至 N+1 为每个资源提供所需的权限。
- 线 1 + i (1 \leq i \leq N) 提供所需的权限 S_i 为 i-th 资源作为长度的字符串 L 组成
0和1。最左边的字符是最高有效位。 - 以下 Q 行给出每个请求。
- 线 N + 1 + j (1 \leq j \leq Q) 给出 j-第一个请求:第一个整数 M_j 表示要访问的资源数量,后跟空格分隔的整数 c_{j,1}, c_{j,2}, \ldots, c_{j,M_j} 代表要访问的资源编号。资源编号是介于 1 和 N 包括在内。同一请求中的资源编号可能会重复。
输出
输出 Q 行。上 j- 第行 (1 \leq j \leq Q),输出允许访问指定的所有资源的权限位串 j第一个请求,当解释为二进制数时具有最小值。将其输出为长度的字符串 L 组成 0 和 1 ,最左边的位是最高有效位(如果长度小于 L,带前导的垫 0s 确保字符串的长度准确 L).
示例输入 1
3 4 3 1010 0110 1001 1 1 2 1 2 3 1 2 3
示例输出 1
1010 1110 1111
示例输入 2
5 8 4 10100000 01010000 00001010 00000101 11000011 1 3 2 1 3 3 2 4 5 4 1 2 3 4
示例输出 2
00001010 10101010 11010111 11111111
示例输入 3
6 16 5 1000000000000001 0100000000000010 0010000000000100 0001000000001000 0000100000010000 1111100000000000 2 1 2 3 1 3 5 1 6 4 2 3 4 5 6 1 2 3 4 5 6
示例输出 3
1100000000000011 1010100000010101 1111100000000000 0111100000011110 1111100000011111