Brincadeira

시프트 레지스터는 비트 벡터의 원소를 한 자리씩 밀어내는 회로다. 입력 비트 하나와 출력 비트 하나가 있고 클록 펄스로 동작한다. 펄스가 들어오면 입력 비트가 벡터의 최상위 비트가 되고, 최하위 비트는 레지스터 출력으로 빠져나가며, 나머지 비트는 모두 최하위 비트 쪽으로 한 자리씩 밀린다.

선형 되먹임 시프트 레지스터(LFSR)는 입력 비트를 펄스 직전 레지스터에 들어 있던 일부 비트의 배타적 논리합으로 정하는 시프트 레지스터다. 되먹임에 쓰이는 비트를 탭이라고 부른다. 아래 그림은 탭이 세 개(비트 0, 3, 5)인 8비트 LFSR이다.

초기 상태	펄스 한 번 뒤의 상태
펄스 두 번 뒤의 상태	펄스 세 번 뒤의 상태

히카르두와 클라우지우는 프로그래밍 대회 최종 결과 발표를 기다리면서 대회장에 있던 LFSR로 논다.

두 사람은 LFSR로 무한 수열을 만든다. 클록 펄스가 울리기 직전마다 레지스터의 비트를 십진수로 바꾼 값이 수열의 원소다. 그림과 같은 LFSR이라면 수열의 앞부분은 $A_0 = 169$ (10101001), $A_1 = 212$ (11010100), $A_2 = 106$ (01101010), $A_3 = 53$ (00110101), $A_4 = 26$ (00011010)이다. 첫 펄스 전의 비트 값이 수열의 첫 원소라는 점에 주의하라.

한 판마다 한 사람이 정수 $X$와 $Y$를 말한다. 그러면 다른 사람은 LFSR이 만든 수열에서 길이가 $Y$ 이상이고 원소의 합이 $X$로 나누어떨어지는 연속 부분수열을 찾아야 한다.

두 사람은 컴퓨터 없이도 답을 척척 찾아내며 이 놀이를 즐긴다. LFSR의 명세와 정수 $X$, $Y$가 주어질 때 조건을 만족하는 연속 부분수열을 찾아라. 없으면 없다고 답하라.

첫째 줄에 정수 다섯 개 $N$, $T$, $A_0$, $X$, $Y$가 공백을 두고 주어진다. $N$은 레지스터의 비트 수 ($2 \le N \le 30$), $T$는 탭의 개수 ($1 \le T \le N$), $A_0$는 LFSR 초기 상태를 십진수로 나타낸 값 ($0 \le A_0 < 2^N$), $X$는 연속 부분수열의 합을 나누어떨어뜨려야 하는 수 ($1 \le X \le 10^6$), $Y$는 연속 부분수열에 들어가야 하는 최소 원소 개수다 ($1 \le Y \le 10^6$). 비트는 최하위 비트인 $0$번부터 최상위 비트인 $N-1$번까지 번호를 매긴다.

둘째 줄에 탭인 비트의 번호 $T$개가 증가하는 순서로 공백을 두고 주어진다. $0$번 비트는 항상 탭이다.

첫째 줄에 고른 연속 부분수열의 첫 원소 인덱스 $I$와 마지막 원소 인덱스 $F$를 공백을 두고 출력한다. 수열의 인덱스는 $0$부터 시작한다. 조건을 만족하는 연속 부분수열이 없으면 impossivel을 출력한다.

답이 여러 개면 $F$가 가장 작은 것을 고르고, 그래도 여러 개면 $I$가 가장 작은 것을 고른다.