의사 난수

많은 응용에서 질 좋은 난수가 필요하고, 암호학에서 특히 그렇다. 진짜 무작위성의 원천으로 방사성 붕괴를 쓰기도 하지만 이 방법은 난수를 얻는 속도가 느리다. 같은 "난수" 수열을 서로 떨어진 두 곳에서 똑같이 만들어야 하는 경우도 많다. 그래서 의사 난수 수열을 대신 쓴다. 의사 난수 수열은 사실 난수가 아니지만 진짜 난수 수열과 구별하기가 매우 어렵다. 예측하기도 어려워야 한다. 앞의 몇 개를 알아도 아직 보지 못한 뒤쪽 원소를 알아내기 어려워야 한다는 뜻이다.

암호기계협회(ACM)가 의사 난수 수열을 만드는 알고리즘을 고안했지만 성능이 어느 정도인지는 아무도 모른다. 이 알고리즘을 검증해 보자.

알고리즘이 내놓는 원소는 모두 $0$ 이상 $B - 1$ 이하의 정수이고, 절차는 다음과 같다.

1. $B$진법으로 적은 씨앗 하나에서 시작한다. 씨앗은 비어 있지 않은 $B$진법 숫자 문자열이고 $0$으로 시작해도 되며, 자릿수가 수백 개일 수도 있다.
2. 맨 뒤 자리(가장 낮은 자리)를 수열의 다음 원소로 출력한다.
3. 이웃한 두 자리의 합을 왼쪽부터 차례로 적어 새 수를 만든다. 각 합은 $B$진법으로 적으므로 합이 $B$ 이상이면 두 자리를 차지한다. $B = 10$이면 $845$는 $8 + 4 = 12$와 $4 + 5 = 9$를 이어 붙인 $129$가 된다.
4. 수가 $B$진법으로 한 자리가 될 때까지 2번과 3번을 반복한다. 그 한 자리가 수열의 마지막 원소이고 알고리즘은 여기서 끝난다.

$B = 10$이고 씨앗이 $845$이면 수는 $845$, $129$, $311$($1 + 2 = 3$, $2 + 9 = 11$), $42$($3 + 1 = 4$, $1 + 1 = 2$), $6$($4 + 2 = 6$) 순으로 바뀐다. 마지막 수는 한 자리이므로 알고리즘이 멈춘다. 이때 나온 의사 난수는 $5$, $9$, $1$, $2$, $6$이다.

검증은 이렇게 한다. 생성기가 내놓은 앞 $L$개 원소와 $L$보다 큰 정수 $T$가 주어진다. 앞 $L$개 원소가 앞 $T$개 원소를 완전히 정하는지 판단하면 된다. 주어진 $L$개 원소를 만드는 씨앗 가운데 원소를 $T$개보다 적게 내놓는 것이 하나라도 있으면 앞 $T$개 원소는 정해지지 않은 것이다. ACM은 검증 절차가 얼마나 튼튼한지 보려고 어떤 씨앗으로도 만들 수 없는 수열도 몇 개 섞어 두었다.

첫 줄에 테스트 케이스의 개수 $N$이 주어진다. 각 테스트 케이스는 세 줄이다. 첫 줄에는 진법 $B$가 주어진다($2 \le B \le 1000$). 둘째 줄에는 정수 $L$($1 \le L \le 100$)과 어떤 수열의 앞 $L$개 원소가 주어진다. 원소는 10진법으로 적으며 모두 $0$ 이상 $B - 1$ 이하이다. 셋째 줄에는 예측할 원소의 위치 $T$가 주어진다($L < T \le 100000$).

각 테스트 케이스마다 한 줄씩 출력한다.

• 주어진 수열을 만드는 씨앗이 없으면 impossible
• 주어진 수열을 만드는 씨앗은 있지만 앞 $L$개 원소가 앞 $T$개 원소를 완전히 정하지 못하면 unpredictable
• 그 밖에는 수열의 $T$번째 원소를 10진법으로