Jungol

길이가 같은 두 개의 이진수 코드w_1과w_2가 있다고 하자.

이 두 코드 사이의 해밍 거리(Hamming distance)는

w_1과w_2의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다.

예를 들어, w_1=010010, w_2 = 011011 이라고 하면, 세 번째 비트와 여섯 번째 비트만 서로 다르므로 해밍 거리는 2이다.

KOI 연구소는 특정 암호문에서 사용되는 총 N개의 이진 코드를 가지고 있다. 각 코드의 길이는 K로 일정하다.

연구소는 이 코드들에 대해 여러 가지 특징을 분석하고 있다. 예를 들어, 다음과 같이 길이가 3인 5개의 이진 코드들이 있다고 하자.

w_1=000, w_2=111, w_3=010, w_4=110, w_5=001

두 코드 w_i와 w_j 사이의 해밍 거리를 hd(w_i, w_j)로 표현한다.

그러면, hd(w_1, w_2) = 3, hd(w_1, w_3) = 1, hd(w_1, w_4) = 2, hd(w_1, w_5) = 1 이다.

당신은 이진 코드들에 대해 해밍 경로(Hamming path)를 찾고자한다.

해밍 경로는 모든 인접한 두 코드사이의 해밍 거리가 1인 경로이다.

위의 예에서 (w_1, w_3, w_4는 길이가 3인 해밍 경로이지만, (w_1, w_5, w_2)는 해밍 경로가 아니다.

두 코드 사이에 해밍 경로가 여러 개가 있을 경우 가장 짧은 경로를 찾고자 한다.

이 문제는 1번 코드에서부터 질의로 주어진 여러 개의 코드까지의 해밍 경로를 각각 구하는 프로그램을 작성하는 것이다.

입력

첫째 줄에는 두 개의 정수 N과 K가 빈칸을 사이에 두고 주어진다(3 \le N \le 100,000, 2\le K\le30).

둘째 줄부터 N개의 줄에는 각 줄마다 길이가 K인 이진 코드가 하나씩 주어진다.

하나의 코드는 빈칸이 없이 주어진다. 코드들은 주어진 순서대로 1부터 N까지의 번호로 구분된다.

코드가 같은 경우는 없다. 그 다음 줄에는 해밍 경로를 찾고자하는 질의의 수인 하나의 정수 M(2\le M\le50)이 주어진다.

그 다음 M개의 줄에는 각 줄마다 한 개의 양의 정수 J(2\le J \le N)가 주어진다.

J는 1번 코드와 J번 코드 사이의 해밍 경로를 구하라는 질의에 해당한다. 주어지는 J는 모두 다르다.

출력

출력은 M개의 줄로 구성된다. 각 줄에는 입력으로 주어진 각 질의에 대한 답을 순서대로 출력한다.

만일 두 코드 사이에 해밍 경로가 존재하면 가장 짧은 경로에 있는 코드들의 번호를 1번 코드부터 차례로 하나의 빈칸을 사이에 두고 출력한다.

답이 여러 개 있으면 그 중에 하나만 출력하고, 경로가 존재하지 않으면 -1을 출력한다.

예제1

출처

KOI 본선 2010 중3

해밍 경로 2초 128MB