405073: GYM101775 G Image Recognition

There are N binary images numbered from 0 to N - 1. Each image contains M pixels numbered from 0 to M - 1. Each pixel is either black or white. Images are pairwise different by at least one pixel.

Now there are some queries. Each query contains a subset of these images. For each query, you want to find a set of pixels that can distinguish every pair of images in it. Two images can be distinguished from each other by a given set of pixels if they have different pixel values in at least one of the given pixels. The number of pixels selected should be less than the number of images in each query.

The first line of the input gives the number of test cases, T. T test cases follow.

The first line of each test case consists of three integers N, M, and Q, indicating the number of images, the number of pixels in each image, and the number of queries. The following N lines describe the content of each image. Each line contains a 01 string of length M representing the content of the image. The following Q lines describe the queries. Each query starts with an integer K_i indicating the number of images of this query, then comes a list of space separated integers indicating the indices of the images.

• 1 ≤ T ≤ 100.
• 1 ≤ N ≤ 2000.
• 1 ≤ M ≤ 4000.
• 1 ≤ Q ≤ 2000.
• 1 ≤ K_i ≤ N.
• .
• .

For each test case, output one line containing "Case #x:", where x is the test case number (starting from 1), then follows Q lines. Each line starts with an integer indicating the number of pixels needed to distinguish the images in the query, then comes a list of space separated integers indicating the indices of the pixels. There could be multiple answers to each query. You may output any of them as long as the number of pixels selected is less than K_i.

1
3 3 4
101
110
001
2 0 1
2 0 2
2 1 2
3 0 1 2

Case #1:
1 1
1 0
1 0
2 0 1