Brincadeira

A shift register is a circuit that moves the elements of a bit vector by one position. It has one input bit and one output bit, and a clock pulse drives it. On a pulse the input bit becomes the most significant bit of the vector, the least significant bit leaves through the register output, and every other bit moves one position toward the least significant bit.

A linear feedback shift register (LFSR) is a shift register whose input bit is the exclusive or of some of the bits held by the register just before the pulse. The bits used in the feedback are called taps. The figure below shows an 8-bit LFSR with three taps (bits 0, 3 and 5).

initial state	state after one pulse
state after two pulses	state after three pulses

While they wait for the final standings of a programming contest, Ricardo and Claudio play with an LFSR they found at the site.

They use the LFSR to generate an infinite sequence of numbers. Just before each clock pulse, the bits of the register are read as a decimal number, and that number is the next element of the sequence. For the LFSR in the figure the sequence starts with $A_0 = 169$ (10101001), $A_1 = 212$ (11010100), $A_2 = 106$ (01101010), $A_3 = 53$ (00110101) and $A_4 = 26$ (00011010). Note that the bits before the first pulse form the first element of the sequence.

In each round one of them says two integers $X$ and $Y$. The other must then find a contiguous subsequence of the sequence generated by the LFSR, of length at least $Y$, whose elements sum to a multiple of $X$.

The two of them manage to enjoy this and to find the answers without a computer. Given the description of an LFSR and the integers $X$ and $Y$, find a valid contiguous subsequence, or report that none exists.

The first line contains five integers $N$, $T$, $A_0$, $X$ and $Y$ separated by spaces. $N$ is the number of bits ($2 \le N \le 30$), $T$ is the number of taps ($1 \le T \le N$), $A_0$ is the decimal representation of the initial state of the LFSR ($0 \le A_0 < 2^N$), $X$ is the value that the sum of the contiguous subsequence must be divisible by ($1 \le X \le 10^6$), and $Y$ is the minimum number of elements in the contiguous subsequence ($1 \le Y \le 10^6$). The bits are numbered from $0$, the least significant bit, to $N-1$, the most significant bit.

The second line contains $T$ integers separated by spaces, the numbers of the bits that are taps, in increasing order. Bit $0$ is always a tap.

Print one line with two integers $I$ and $F$, the indices of the first and the last element of the chosen contiguous subsequence. The sequence is indexed from $0$. If no valid subsequence exists, print the word impossivel.

If more than one subsequence works, choose the one that minimizes $F$. If several still remain, choose the one that minimizes $I$.