Problem
TV 채널 중 하나에서 매주 다음 복권이 열립니다. 주중에 참가자들은 베팅을 합니다. 각 베팅은 기본 K 번호 시스템에서 M 자리 번호의 이름을 지정하는 것으로 구성됩니다(즉, 실제로 각 참가자는 M 자리 이름을 지정하며 각 번호는 0에서 K & 빼기, 1 범위에 있음). 숫자 앞에 0이 허용됩니다.
어느 시점에서 현재 추첨에 대한 베팅이 종료되고 그 후 진행자가 TV에서 당첨 번호를 발표합니다(이 역시 K-ary 번호 시스템의 M자리 번호입니다). 그 후, 번호의 첫 번째 숫자가 호스트가 지정한 숫자의 첫 번째 숫자와 일치하는 TV 시청자는 A
1 루블의 금액으로 승리합니다. — 의 처음 두 자리 숫자와 일치하는 사람 A
2 루블을 받습니다(동시에 플레이어가 두 번째 숫자가 일치했지만 첫 번째 숫자가 일치하지 않으면 아무 것도 받지 못합니다). 마찬가지로 처음 세 자리 숫자를 맞힌 사람은 A
3 루블을 받습니다. 등등. 전체 숫자를 추측한 사람들은 Am 루블을 완전히 받습니다. 또한 플레이어가 첫 번째 t 숫자를 맞추면 A
t 루블을 받지만 t−1, t−2 등을 맞추면 상을 받지 않습니다. 숫자. 플레이어가 첫 번째 숫자를 추측하지 않으면 아무것도 얻지 못합니다.
시청자의 알려진 내기가 주어졌을 때 조직 회사가 상금으로 최소 금액을 지불하기 위해 TV 발표자가 이름을 지정해야 하는 번호를 찾는 프로그램을 작성하십시오. 귀하의 편의를 위해 플레이어의 베팅은 이미 내림차순이 아닌 순서로 정렬되어 있습니다.
입력
첫 번째 줄에는 숫자 N(베팅을 한 TV 시청자 수, 1N100000), M(숫자 길이 1M10) K(숫자 체계 2 ≤ K ≤ 10의 밑수)가 포함됩니다. 다음 줄은 M개의 정수 A
1, A
2, ..., A
M을 포함하며 첫 번째, 처음 두 개, ... , 모든 숫자(1 ≤ A
1 ≤ A
2 ≤ ... ≤ A
M ≤ 100000 ) . 다음 N 행 각각에는 하나의 M 자리 K-ary 숫자가 포함됩니다. 숫자는 내림차순이 아닙니다.
출판물
첫 번째 줄에 원하는 숫자를 인쇄하고(해가 여러 개인 경우 - 그중 하나를 인쇄) 두 번째 줄에 - 첫날 TV 발표자를 지명 할 때 상금으로 지불해야 할 금액.
예
<헤드>
| # |
입력 |
출력 |
<몸>
| 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 |