{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eFamous secure shell (ssh) protocol is often used to provide remote access to Unix systems. In ssh protocol\nall communcations with the server are encrypted using a strong cipher, so it is considered essentially\nimpossible to eavesdrop them.\u003c/p\u003e\n\u003cp\u003eHowever, cryptoanalysts have recently found a vulnerability that can be used to learn the user\u0027s password\nwhen the ssh session is established. The drawback is that when the characters are typed slowly, it is\npossible that each character is sent to the server in his own network packet. Analyzing the time intervals\nbetween consecutive packets and comparing them to typical intervals between typing various characters\nby the user, it may be possible to determine the most probable password.\u003c/p\u003e\n\u003cp\u003eYou are given the time intervals between consecutive packets in some password sending session and the\ntypical intervals between typing all possible pairs of characters. Your task is to determine the most\nprobable password, assuming that each character of the password was sent in its own packet.\u003c/p\u003e\n\u003cp\u003eThe probability of some string to be the password is determined in the following way. Let the sequence\nof 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 \u003d p1p2...pl its unlikeness to the given intervals sequence is\u003c/p\u003e\n\n\u003ccenter\u003e\nU(p) \u003d | a[1] - t[p1][p2] | + | a[2] - t[p2][p3] | + . . . + | a[l-1] - t[pl-1][pl] |\n\u003c/center\u003e\n\n\u003cp\u003eThe less is the unlikeness of the password -- the more probable it is.\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eInput:\u003c/b\u003e\u003c/p\u003e\n\n\u003cp\u003eThe input consists of several test cases\u003c/p\u003e\n\n\u003cp\u003eThe first line of each test case contains \u003ci\u003el\u003c/i\u003e -- the length of the password, and \u003ci\u003em\u003c/i\u003e -- the number of different characters that can be used in password (2 \u0026lt;\u003d l \u0026lt;\u003d 100, 2 \u0026lt;\u003d m \u0026lt;\u003d 26). The characters used in the password\nare the first m small letters of the English alphabet.\n\u003c/p\u003e\u003cp\u003eThe second line of each test case contains \u003ci\u003el-1\u003c/i\u003e integer numbers: a[1], a[2], ... , a[l-1] (1 \u0026lt;\u003d a[i] \u0026lt;\u003d 1000). The following m lines contain m integer numbers each and represent the typical intervals between typing the\ncharacters, j-th number of the i-th line is the interval between typing i-th and j-th characters of the\nalphabet (1 \u0026lt;\u003d t[i][j] \u0026lt;\u003d 1000).\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eOutput:\u003c/b\u003e\u003c/p\u003e\n\n\u003cp\u003eFor each test case, output the most probable password in a line. If there are several possible answers, output any one.\u003c/p\u003e\n\n\u003cb\u003eSample Input:\u003c/b\u003e\u003cpre\u003e7 3\n3 4 4 6 3 5\n1 3 4\n5 1 2\n6 3 1\n\u003c/pre\u003e\n\n\u003cb\u003eSample Output:\u003c/b\u003e\u003cpre\u003eabacaba\n\u003c/pre\u003e\n\n\n\n\n\u003cbr\u003e\n"}}]}