{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eAlthough Haneen was able to solve the LCS problem, Dr. Ibrahim is suspicious about whether she really understands the LCS problem or not. He believes that she can\u0027t write the code on her own, but can only translate the LCS pseudo-code given in class into C++ code without really understanding how it works. Here is the pseudo-code Dr. Ibrahim gave in class: \u003c/p\u003e\u003cpre class\u003d\"verbatim\"\u003efunction LCS (A[1..R], B[1..C])\u003cbr\u003e DP \u003d array(0..R, 0..C)\u003cbr\u003e for i :\u003d 0..R\u003cbr\u003e DP[i,0] \u003d 0\u003cbr\u003e for j :\u003d 0..C\u003cbr\u003e DP[0,j] \u003d 0\u003cbr\u003e for i :\u003d 1..R\u003cbr\u003e for j :\u003d 1..C\u003cbr\u003e if A[i] \u003d B[j]\u003cbr\u003e DP[i,j] :\u003d DP[i-1,j-1] + 1\u003cbr\u003e else\u003cbr\u003e DP[i,j] :\u003d max(DP[i,j-1], DP[i-1,j])\u003cbr\u003e return DP[R,C]\u003cbr\u003e\u003c/pre\u003e\u003cp\u003eTo verify that Haneen understands the LCS problem, Dr. Ibrahim asked her to solve the following problem:\u003c/p\u003e\u003cp\u003eAfter running the above LCS code on two strings \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003c/span\u003e, the 2D array \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eDP\u003c/i\u003e\u003c/span\u003e is filled with values. Given the 2D array \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eDP\u003c/i\u003e\u003c/span\u003e, can you guess what \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003c/span\u003e are? Any two strings \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003c/span\u003e that will produce the given table and contain only lowercase English letters are acceptable.\u003c/p\u003e\u003cp\u003eCan you help Haneen solve this problem?\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of input contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eR\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eC\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003eR\u003c/i\u003e, \u003ci\u003eC\u003c/i\u003e ≤ 25)\u003c/span\u003e, the length of the strings A and B, respectively.\u003c/p\u003e\u003cp\u003eEach of the following \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eR\u003c/i\u003e + 1\u003c/span\u003e lines contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eC\u003c/i\u003e + 1\u003c/span\u003e integers, these lines represent the 2D array DP.\u003c/p\u003e\u003cp\u003eIt\u0027s guaranteed that the given table was produced by running the algorithm on two strings that contain only lowercase English letters.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e on the first line and string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003c/span\u003e on the second line. Both strings should contain only lowercase English letters.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 4\n0 0 0 0 0\n0 0 1 1 1\n0 0 1 1 2\n0 1 1 1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eabc\ncadb\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}