선형 피드백 시프트 레지스터

시프트 레지스터는 비트 벡터의 원소를 한 칸씩 옮기는 회로다. 시프트 레지스터에는 입력 한 비트와 출력 한 비트가 있고, 클록 펄스에 맞춰 동작한다. 펄스가 발생하면 입력 비트는 벡터의 최상위 비트(비트 $N-1$)가 되고, 최하위 비트(비트 0)는 레지스터의 출력으로 밀려나며, 나머지 비트는 모두 최하위 비트 쪽(출력 쪽)으로 한 칸씩 이동한다.

선형 피드백 시프트 레지스터(LFSR)는 클록 펄스 직전 레지스터의 몇몇 비트를 XOR한 값이 입력 비트가 되는 시프트 레지스터다. 피드백에 쓰이는 비트를 탭이라고 한다. 아래 그림은 탭이 세 개(비트 0, 3, 5)인 8비트 LFSR이 펄스를 세 번 받는 모습이다. 오른쪽 끝 칸이 비트 0이다.

상태를 정수 $s$로 나타내면, 펄스 한 번 뒤의 상태는 $\lfloor s/2 \rfloor + f \cdot 2^{N-1}$이다. 여기서 $f$는 $s$의 탭 비트를 모두 XOR한 값이다.

LFSR의 비트 수, 피드백에 쓰이는 비트, 초기 상태와 최종 상태가 주어질 때, 초기 상태에서 출발한 LFSR이 최종 상태에 도달하려면 클록 펄스가 최소 몇 번 필요한지 구하는 프로그램을 작성하시오. 도달할 수 없다면 그 사실을 판별해야 한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 세 줄이다. 첫째 줄에 비트 수 $N$($2 \le N \le 32$)과 탭의 개수 $T$($2 \le T \le N$)가 주어진다. 비트는 0(최하위 비트)부터 $N-1$(최상위 비트)까지의 정수로 구분한다. 둘째 줄에는 탭인 비트의 번호 $T$개가 공백으로 구분되어 오름차순으로 주어진다. 비트 0은 항상 탭이다. 셋째 줄에는 LFSR의 초기 상태 $I$와 최종 상태 $F$가 16진수로 공백 하나를 사이에 두고 주어진다. 두 값은 $N$비트로 나타낼 수 있고, 16진수의 영문자는 대문자일 수도 소문자일 수도 있다.

입력의 마지막 줄에는 0 두 개가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 한 줄을 출력한다. 초기 상태에서 최종 상태에 도달할 수 있으면, LFSR이 최종 상태에 도달하는 데 필요한 클록 펄스 횟수의 최솟값을 정수 하나로 출력한다. 도달할 수 없으면 문자 * 하나만 출력한다.