해밍 경로

길이가 같은 두 이진 코드 w1과 w2가 있다. 두 코드의 해밍 거리(Hamming distance)는 왼쪽부터 같은 위치의 비트를 비교했을 때 서로 다른 위치의 개수이다. 예를 들어 w1 = 010010, w2 = 011011이면 세 번째 비트와 여섯 번째 비트만 다르므로 해밍 거리는 2이다.

어떤 연구소는 암호문에 쓰이는 N개의 이진 코드를 가지고 있다. 모든 코드의 길이는 K로 같다. 코드들은 입력된 순서대로 w1, w2, ..., wN이라고 부른다. 예를 들어 길이가 3인 다음 다섯 코드가 있다고 하자.

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

두 코드 wi와 wj 사이의 해밍 거리를 hd(wi, wj)라고 쓰면, hd(w1, w2) = 3, hd(w1, w3) = 1, hd(w1, w4) = 2, hd(w1, w5) = 1이다.

해밍 경로는 경로에서 서로 이웃한 두 코드의 해밍 거리가 항상 1인 경로이다. 위 코드들에서 (w1, w3, w4)는 길이가 3인 해밍 경로이지만, (w1, w5, w2)는 해밍 경로가 아니다. 두 코드 사이에 해밍 경로가 여러 개 있으면 가장 짧은 경로를 구한다.

1번 코드에서 각 질의로 주어진 코드까지의 해밍 경로를 구하는 프로그램을 작성하라.

첫째 줄에 두 정수 N과 K가 공백으로 구분되어 주어진다(3 <= N <= 100,000, 2 <= K <= 30). 다음 N개의 줄에는 길이가 K인 이진 코드가 한 줄에 하나씩 주어진다. 코드는 공백 없이 주어지며, 입력 순서대로 1번부터 N번까지 번호가 붙는다. 같은 코드는 주어지지 않는다.

그다음 줄에 해밍 경로를 찾을 질의의 수 M이 주어진다(2 <= M <= 50). 이어지는 M개의 줄에는 양의 정수 J가 하나씩 주어진다(2 <= J <= N). 이는 1번 코드와 J번 코드 사이의 해밍 경로를 구하라는 질의이다. 주어지는 J는 모두 다르다.

질의마다 한 줄씩, 입력으로 주어진 순서대로 답을 출력한다. 두 코드 사이에 해밍 경로가 존재하면 가장 짧은 경로에 포함된 코드 번호를 1번 코드부터 차례대로 공백 하나로 구분해 출력한다. 가능한 답이 여러 개이면 그중 아무거나 하나만 출력한다. 경로가 존재하지 않으면 -1을 출력한다.