Problem
Di salah satu saluran TV, loteri seterusnya diadakan setiap minggu. Sepanjang minggu, peserta membuat pertaruhan mereka. Setiap pertaruhan terdiri daripada menamakan beberapa nombor M-digit dalam sistem nombor asas K (iaitu, sebenarnya, setiap peserta menamakan digit M, setiap satunya terletak dalam julat dari 0 hingga K & tolak; 1). Sifar pendahuluan dibenarkan dalam nombor.
Pada satu ketika, pertaruhan pada cabutan semasa berakhir, dan selepas itu, penyampai mengumumkan nombor yang menang di televisyen (ini juga nombor M-digit dalam sistem nombor K-ary). Selepas itu, penonton TV tersebut, yang digit pertama nombor mereka bertepatan dengan digit pertama nombor yang dinamakan oleh hos, menerima kemenangan dalam jumlah A
1 rubel. Mereka yang memadankan dua digit pertama — terima A
2 rubel (pada masa yang sama, jika pemain mempunyai digit kedua yang dipadankan, tetapi digit pertama tidak sepadan, dia tidak menerima apa-apa). Begitu juga, mereka yang meneka tiga digit pertama menerima A
3 rubel. Dan sebagainya. Mereka yang meneka nombor keseluruhan menerima Rubel Am sepenuhnya. Selain itu, jika pemain meneka digit t pertama, maka dia menerima A
t rubel, tetapi tidak menerima hadiah untuk meneka t&tolak;1, t&tolak;2, dsb. digit. Jika pemain tidak meneka nombor pertama, dia tidak mendapat apa-apa.
Tulis program yang, memandangkan pertaruhan yang diketahui dibuat oleh penonton, mencari nombor yang penyampai TV mesti namakan agar syarikat penganjur membayar jumlah minimum sebagai kemenangan. Untuk kemudahan anda, pertaruhan yang dibuat oleh pemain sudah diisih dalam susunan tidak menurun.
Input
Baris pertama mengandungi nombor N (bilangan penonton TV yang membuat pertaruhan mereka, 1N100000), M (panjang nombor 1M10) K (pangkal sistem nombor 2 ≤ K ≤ 10). Baris seterusnya mengandungi M integer A
1, A
2, ..., A
M, menyatakan bayaran jika hanya yang pertama, dua yang pertama , ... , semua digit (1 ≤ A
1 ≤ A
2 ≤ ... ≤ A
M ≤ 100000 ) . Setiap baris N seterusnya mengandungi satu nombor K-ary M-digit. Nombor-nombor berada dalam susunan tidak menurun.
Cetakan
Pada baris pertama cetak nombor yang dikehendaki (jika terdapat beberapa penyelesaian — cetak mana-mana daripadanya), dan pada baris kedua — jumlah yang, apabila menamakan penyampai TV pada hari pertama, perlu dibayar sebagai kemenangan.
Contoh
| # |
Input |
Output |
| 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 |