import std.stdio, std.algorithm, std.array, std.conv; void main() { auto NM = readln.split.to!(long[]); auto N = NM[0], M = NM[1]; auto T = readln.split.to!(long[]); long[][] A, P; foreach (_; 0 .. N) { auto row = readln.split.to!(long[]); A ~= row; P ~= new long[N]; } foreach (i; 0 .. N) foreach (j; 0 .. N) if (i == j) P[i][j] = 0; else P[i][j] = -long.max; long p = 1; while (p <= M) { if ((M&p) != 0) P = multiply(P, A); p *= 2; A = multiply(A, A); } foreach (i; 0 .. N) { long ans; foreach (j; 0 .. N) ans = max(ans, T[j] + P[j][i]); write(ans, " "); } writeln; } long inner_prod(long[] a, long[] b) { long c; foreach (i; 0 .. a.length) { c = max(c, a[i] + b[i]); } return c; } long[][] multiply(long[][] a, long[][] b) { long[][] c; const N = a.length; c.length = N; foreach (i; 0 .. N) { c[i].length = N; foreach (j; 0 .. N) foreach (k; 0 .. N) c[i][j] = max(c[i][j], a[i][k] + b[k][j]); } return c; }