Problem
Trên một trong những kênh truyền hình, xổ số tiếp theo được tổ chức hàng tuần. Trong tuần, những người tham gia đặt cược. Mỗi lần đặt cược bao gồm việc đặt tên cho một số có M chữ số trong hệ thống số K cơ sở (trên thực tế, mỗi người tham gia đặt tên cho M chữ số, mỗi chữ số nằm trong phạm vi từ 0 đến K & trừ; 1). Cho phép sử dụng số 0 ở đầu trong số.
Tại một số thời điểm, việc đặt cược vào kết quả hòa hiện tại kết thúc và sau đó, người thuyết trình công bố số trúng thưởng trên truyền hình (đây cũng là một số có chữ số M trong hệ thống số K-ary). Sau đó, những người xem truyền hình có chữ số đầu tiên trong số của họ trùng với chữ số đầu tiên của số do người dẫn chương trình đặt tên sẽ nhận được tiền thắng với số tiền là A
1 rúp. Những người khớp với hai chữ số đầu tiên của — nhận được A
2 rúp (đồng thời, nếu người chơi khớp chữ số thứ hai nhưng chữ số đầu tiên không khớp thì anh ta không nhận được gì). Tương tự, những người đoán đúng ba chữ số đầu tiên sẽ nhận được A
3 rúp. Và như thế. Những người đoán đúng toàn bộ số nhận được Am rúp. Hơn nữa, nếu người chơi đoán t chữ số đầu tiên, thì anh ta nhận được A
t rúp, nhưng không nhận được giải thưởng khi đoán t&trừ 1, t&trừ 2, v.v. chữ số. Nếu người chơi không đoán được số đầu tiên, anh ta sẽ không nhận được gì.
Viết một chương trình, với số tiền đặt cược đã biết của người xem, tìm ra con số mà người dẫn chương trình truyền hình phải đặt tên để công ty tổ chức thanh toán số tiền tối thiểu dưới dạng tiền thắng cược. Để thuận tiện cho bạn, cược của người chơi đã được sắp xếp theo thứ tự không giảm dần.
Đầu vào
Dòng đầu tiên chứa các số N (số người xem TV đã đặt cược, 1N100000), M (độ dài của các số 1M10) K (cơ số của hệ thống số 2 ≤ K ≤ 10). Dòng tiếp theo chứa M số nguyên A
1, A
2, ..., A
M, chỉ định kết quả nếu chỉ có số đầu tiên, hai số đầu tiên, ... , tất cả các chữ số (1 ≤ A
1 ≤ A
2 ≤ ... ≤ A
M ≤ 100000 ) . Mỗi dòng trong số N dòng tiếp theo chứa một số K-ary có M chữ số. Các số sắp theo thứ tự không giảm.
Dấu ấn
Trên dòng đầu tiên, in số mong muốn (nếu có một số giải pháp — in bất kỳ giải pháp nào trong số đó) và trên dòng thứ hai — số tiền mà khi gọi tên người dẫn chương trình truyền hình vào ngày đầu tiên sẽ phải trả dưới dạng tiền thắng cược.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
10 3 2
1 3 100
000
000
001
010
100
100
100
100
110
111 |
011
6 |
| 2 |
1 1 10
100
0 |
1
0 |