Hamming Path

Let w1 and w2 be two binary codes of the same length. The Hamming distance between them is the number of positions whose bits differ when the two codes are compared from left to right. For example, if w1 = 010010 and w2 = 011011, only the third and sixth bits differ, so the Hamming distance is 2.

A research lab has N binary codes used in a cipher. Every code has the same length K. The codes are named w1, w2, ..., wN in input order. For example, suppose the following five codes have length 3.

• w1 = 000
• w2 = 111
• w3 = 010
• w4 = 110
• w5 = 001

If hd(wi, wj) denotes the Hamming distance between wi and wj, then hd(w1, w2) = 3, hd(w1, w3) = 1, hd(w1, w4) = 2, and hd(w1, w5) = 1.

A Hamming path is a path in which every pair of adjacent codes has Hamming distance 1. In the example above, (w1, w3, w4) is a Hamming path of length 3, but (w1, w5, w2) is not a Hamming path. If several Hamming paths exist between two codes, find a shortest one.

Write a program that finds, for each query, a Hamming path from code 1 to the queried code.

The first line contains two integers N and K separated by a space (3 <= N <= 100,000, 2 <= K <= 30). Each of the next N lines contains one binary code of length K. A code is given without spaces. The codes are numbered from 1 to N in input order, and no two codes are identical.

The next line contains one integer M, the number of queries (2 <= M <= 50). Each of the following M lines contains one positive integer J (2 <= J <= N). The query asks for a Hamming path between code 1 and code J. All given J values are distinct.

Print one answer line for each query, in the same order as the input. If a Hamming path exists between the two codes, print the code numbers on a shortest path starting from code 1, separated by single spaces. If there is more than one valid answer, print any one of them. If no path exists, print -1.