Tôi muốn tạo một trang web chơi poker trực tuyến. Một thành phần rất quan trọng của hệ thống như vậy là bộ tạo số ngẫu nhiên. Nó cần phải nhanh và đủ ngẫu nhiên. Đây là một phương án thỏa hiệp mà tôi đã nghĩ ra. Tôi cần một cách để tạo các số ngẫu nhiên có độ dài tối đa là \(D\). Kế hoạch của tôi là chọn một số nguyên tố \(P \le 10^D\). Tôi cũng sẽ chọn các số nguyên không âm \(A\) và \(B\). Cuối cùng, tôi sẽ chọn một hạt giống (seed) là số nguyên \(S\) nằm trong khoảng từ \(0\) đến \(P-1\), bao gồm cả hai đầu.

Để xuất ra chuỗi các số giả ngẫu nhiên của mình, đầu tiên tôi sẽ xuất ra \(S\) và sau đó tính giá trị mới của \(S\) như sau:
S := (A*S + B) mod P.

Sau đó, tôi sẽ xuất giá trị mới của \(S\) là số tiếp theo trong chuỗi và cập nhật \(S\) một lần nữa bằng cách sử dụng cùng một công thức. Tôi có thể lặp lại việc này bao nhiêu lần tùy ý.

Bạn có nghĩ rằng đây là một bộ tạo số ngẫu nhiên tốt không? Bạn có thể viết một chương trình nhận vào \(K\) phần tử liên tiếp của một chuỗi được tạo bởi bộ tạo số ngẫu nhiên của tôi và in ra phần tử tiếp theo của chuỗi đó không?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo. Mỗi bộ bắt đầu bằng một dòng chứa \(D\) và \(K\). Dòng tiếp theo chứa \(K\) phần tử liên tiếp được tạo bởi bộ tạo số ngẫu nhiên loại được mô tả ở trên.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự của bộ thử nghiệm (bắt đầu từ 1) và y là số tiếp theo trong chuỗi, hoặc chuỗi "I don't know." nếu câu trả lời không duy nhất.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le K \le 10\).
• \(K\) số nguyên sẽ là các phần tử liên tiếp của một chuỗi được tạo bởi bộ tạo số ngẫu nhiên thuộc loại mô tả ở trên.

Phân nhóm

• Small dataset (Test set 1 - Visible): \(1 \le D \le 4\).
• Large dataset (Test set 2 - Hidden): \(1 \le D \le 6\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
2 10
0 1 2 3 4 5 6 7 8 9
3 1
13
1 5
6 6 6 6 6

Case #1: 10
Case #2: I don't know.
Case #3: 6

Nguồn

Google Code Jam 2010, Vòng 3, bài De-RNG-ed.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.