Linear Feedback Shift Register

A shift register is a circuit that shifts the elements of a bit vector by one position. A shift register has one input bit and one output bit, and a clock pulse drives it. When a pulse occurs, the input bit becomes the most significant bit of the vector (bit $N-1$), the least significant bit (bit 0) is pushed out as the output of the register, and every other bit moves one position toward the least significant bit (toward the output).

A linear feedback shift register (LFSR) is a shift register whose input bit is the exclusive OR (XOR) of some of the register's bits just before the clock pulse. The bits used for the feedback are called taps. The figure below shows an 8-bit LFSR with three taps (bits 0, 3, and 5) over three pulses. The rightmost cell is bit 0.

If the state is written as an integer $s$, the state after one pulse is $\lfloor s/2 \rfloor + f \cdot 2^{N-1}$, where $f$ is the XOR of the tap bits of $s$.

Write a program that, given the number of bits of an LFSR, the bits that are taps, an initial state, and a final state, finds the minimum number of clock pulses the LFSR needs to go from the initial state to the final state, or determines that this is impossible.

The input contains several test cases. Each test case has three lines. The first line contains two integers $N$ and $T$: the number of bits ($2 \le N \le 32$) and the number of taps ($2 \le T \le N$). Bits are numbered with integers from 0 (the least significant bit) to $N-1$ (the most significant bit). The second line contains $T$ space-separated integers in increasing order: the numbers of the bits that are taps. Bit 0 is always a tap. The third line contains two hexadecimal numbers $I$ and $F$ separated by a single space: the initial state and the final state of the LFSR. Both values fit in $N$ bits, and the hexadecimal letters can be uppercase or lowercase.

The last line of the input contains two zeros separated by a space.

For each test case, print one line. If the final state can be reached from the initial state, print a single integer: the minimum number of clock pulses the LFSR needs to reach the final state. Otherwise, print only the character *.