/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 266 点
問題文
高橋君はある会社のシステム管理者です。この会社には N 種類のリソースがあり、それぞれのリソースにアクセスするために必要な権限が設定されています。権限は L 個の権限項目からなり、i 番目のリソースに必要な権限は、長さ L のビット列 S_i で表されます。ビット列は 0 と 1 からなる文字列であり、左端のビットを最上位ビット（MSB）とします。ビット列の第 p ビット（1 \leq p \leq L、左端を第 1 ビットとする）が 1 であるとき、そのリソースへのアクセスには第 p 権限項目が必要であることを意味します。
社員に付与するアクセス権限もまた長さ L のビット列 K で表されます。ある社員がリソース i にアクセスできる条件は、そのリソースが要求するすべての権限項目を社員が持っていること、すなわち各ビット位置について S_i のビットが 1 ならば K の同じ位置のビットも 1 であること（ビットごとの AND を取ったとき K \mathbin{\&} S_i = S_i が成り立つこと）です。
青木君は会社のセキュリティ担当で、不必要に大きな権限を付与しない運用を推進しています。青木君は高橋君に 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 は
0と1からなる長さ L の文字列である（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}
- 1 行目には、リソースの種類数を表す整数 N、ビット列の長さを表す整数 L、依頼の個数を表す整数 Q が、スペース区切りで与えられる。
- 2 行目から N+1 行目では、各リソースの必要権限が与えられる。
- 1 + i 行目（1 \leq i \leq N）では、i 番目のリソースの必要権限 S_i が、
0と1からなる長さ L の文字列として与えられる。文字列の左端が最上位ビットである。 - 続く 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 に満たない場合は先頭を 0 で埋め、必ず長さ 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
Score : 266 pts
Problem Statement
Takahashi is a system administrator at a company. The company has N types of resources, and each resource has a set of required permissions to access it. Permissions consist of L permission items, and the permissions required for the i-th resource are represented by a bit string S_i of length L. A bit string is a string consisting of 0 and 1, where the leftmost bit is the most significant bit (MSB). When the p-th bit (1 \leq p \leq L, counting the leftmost bit as the 1st bit) of the bit string is 1, it means that the p-th permission item is required to access that resource.
The access permissions granted to an employee are also represented by a bit string K of length L. The condition for an employee to access resource i is that the employee possesses all permission items required by that resource. In other words, for each bit position, if the bit of S_i is 1, then the bit at the same position in K must also be 1 (i.e., the bitwise AND satisfies K \mathbin{\&} S_i = S_i).
Aoki is the company's security officer and promotes a policy of not granting unnecessarily broad permissions. Aoki has given Takahashi Q requests. In the j-th request (1 \leq j \leq Q), the numbers of M_j resources that a certain employee needs to access are specified: c_{j,1}, c_{j,2}, \ldots, c_{j,M_j} (resource numbers may be duplicated within the same request). Among all permission bit strings K that allow access to all specified resources, find the one whose value is minimized when the bit string is interpreted as a binary number.
Note that a permission bit string that allows access to all specified resources always exists (for example, a bit string with all bits set to 1 satisfies the condition).
Constraints
- 1 \leq N \leq 10^5
- 1 \leq L \leq 64
- 1 \leq Q \leq 10^5
- S_i is a string of length L consisting of
0and1(1 \leq i \leq N) - M_j is the number of resources specified in the j-th request, and 1 \leq M_j \leq N (1 \leq j \leq Q)
- c_{j,k} is a resource number specified in the j-th request, and 1 \leq c_{j,k} \leq N (1 \leq j \leq Q, 1 \leq k \leq M_j)
- Resource numbers may be duplicated within the same request
- \sum_{j=1}^{Q} M_j \leq 10^5
- S_i is given as a string; all other inputs are integers
Input
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}
- The first line contains three space-separated integers: N representing the number of resource types, L representing the length of the bit strings, and Q representing the number of requests.
- Lines 2 through N+1 give the required permissions for each resource.
- Line 1 + i (1 \leq i \leq N) gives the required permissions S_i for the i-th resource as a string of length L consisting of
0and1. The leftmost character is the most significant bit. - The following Q lines give each request.
- Line N + 1 + j (1 \leq j \leq Q) gives the j-th request: first an integer M_j representing the number of resources to access, followed by space-separated integers c_{j,1}, c_{j,2}, \ldots, c_{j,M_j} representing the resource numbers to access. Resource numbers are integers between 1 and N inclusive. Resource numbers may be duplicated within the same request.
Output
Output Q lines. On the j-th line (1 \leq j \leq Q), output the permission bit string that allows access to all resources specified in the j-th request and has the minimum value when interpreted as a binary number. Output it as a string of length L consisting of 0 and 1 with the leftmost bit being the most significant bit (if the length is less than L, pad with leading 0s to ensure the string is exactly of length L).
Sample Input 1
3 4 3 1010 0110 1001 1 1 2 1 2 3 1 2 3
Sample Output 1
1010 1110 1111
Sample Input 2
5 8 4 10100000 01010000 00001010 00000101 11000011 1 3 2 1 3 3 2 4 5 4 1 2 3 4
Sample Output 2
00001010 10101010 11010111 11111111
Sample Input 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
Sample Output 3
1100000000000011 1010100000010101 1111100000000000 0111100000011110 1111100000011111