Problem
在其中一个电视频道上，每周都会举行下一次抽奖。在一周内，参与者下注。每个投注包括在基数 K 数字系统中命名一些 M 位数字（也就是说，事实上，每个参与者命名 M 个数字，每个数字都在 0 到 K & 负 1 的范围内）。数字中允许有前导零。
某时，本期开奖结束，主持人在电视上宣布中奖号码（这也是K进制中的M位号码）。之后，那些他们号码的第一位数字与主持人命名的号码的第一位数字相符的电视观众将获得 A
1 卢布的奖金。匹配前两位数字的人收到 A
2 卢布（同时，如果玩家的第二个数字匹配，但第一个数字不匹配，他不会收到任何东西）。同样，猜中前三位数字的人将获得 A
3 卢布。等等。猜对全部数字的人将获得 Am 卢布。此外，如果玩家猜中了前 t 个数字，那么他将获得 A
t 卢布，但不会因猜中 t−1、t−2 等而获得奖励。数字。如果玩家没有猜到第一个数字，他将一无所获。
编写一个程序，根据已知的观众下注，找到电视节目主持人必须说出的数字，以便组织公司支付最低金额作为奖金。为了您的方便，玩家的投注已经按照非降序排列。
输入
第一行包含数字 N（下注的电视观众人数，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 进制数。数字按非递减顺序排列。
印记
在第一行打印所需的数字（如果有多个解决方案 - 打印其中任何一个），并在第二行 - mdash;在第一天命名电视节目主持人时，必须支付的金额作为胜利。
例子
<头>
| # |
输入 |
输出 |
<正文>
| 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 |