High School Programming League Problems Archive

Given a Fibonacci linear feedback shift register (LFSR) please emulate its behaviour.

Input

First t<100, the number of test cases. In each of the following t lines:
1<l<=1024 - the length of the register (the number of bits),
seed - the initial value of the LFSR in binary format,
0<p<l - the number of taps (bits which influence the input),
p₁,p₂,...,p_p - the taps in increasing order in decimal format, 0<p_i<=l.

Output

Please output, byte by byte, the first 128 output bits of the register in hexadecimal format.

Example

Input:
2
3 010 2 2 3
5 00110 3 1 3 5

Output:
A7 D3 E9 74 3A 9D 4E A7 D3 E9 74 3A 9D 4E A7 D3
85 9B C2 4D E1 A6 70 53 B8 29 DC 14 6E 0A 37 85 

Scoring

By solving this problem you score 10 points.