Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2565
Cracking SSH

Time Limit: 2 Seconds      Memory Limit: 65536 KB      Special Judge

Famous secure shell (ssh) protocol is often used to provide remote access to Unix systems. In ssh protocol all communcations with the server are encrypted using a strong cipher, so it is considered essentially impossible to eavesdrop them.

However, cryptoanalysts have recently found a vulnerability that can be used to learn the user's password when the ssh session is established. The drawback is that when the characters are typed slowly, it is possible that each character is sent to the server in his own network packet. Analyzing the time intervals between consecutive packets and comparing them to typical intervals between typing various characters by the user, it may be possible to determine the most probable password.

You are given the time intervals between consecutive packets in some password sending session and the typical intervals between typing all possible pairs of characters. Your task is to determine the most probable password, assuming that each character of the password was sent in its own packet.

The probability of some string to be the password is determined in the following way. Let the sequence of time intervals given be a[1], a[2], ... , a[l-1]. Let the typical time interval between typing characters c and d be t[c][d]. For the password p = p1p2...pl its unlikeness to the given intervals sequence is

U(p) = | a[1] - t[p1][p2] | + | a[2] - t[p2][p3] | + . . . + | a[l-1] - t[pl-1][pl] |

The less is the unlikeness of the password -- the more probable it is.


The input consists of several test cases

The first line of each test case contains l -- the length of the password, and m -- the number of different characters that can be used in password (2 <= l <= 100, 2 <= m <= 26). The characters used in the password are the first m small letters of the English alphabet.

The second line of each test case contains l-1 integer numbers: a[1], a[2], ... , a[l-1] (1 <= a[i] <= 1000). The following m lines contain m integer numbers each and represent the typical intervals between typing the characters, j-th number of the i-th line is the interval between typing i-th and j-th characters of the alphabet (1 <= t[i][j] <= 1000).


For each test case, output the most probable password in a line. If there are several possible answers, output any one.

Sample Input:
7 3
3 4 4 6 3 5
1 3 4
5 1 2
6 3 1
Sample Output:

Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #4
Submit    Status