축구 마라톤

N개의 팀이 축구 마라톤에 참가한다. 총 K번의 경기를 한 번에 한 경기씩 진행한다.

첫 경기는 1번 팀과 2번 팀이 한다. 각 경기에서 진 팀은 경기장을 떠나고, 이긴 팀은 남아서 다음 순서의 팀과 경기한다.

N번 팀까지 들어오는 순서가 진행되면 다시 1번 팀부터 순서대로 진행한다. 들어올 차례인 팀이 현재 승자로서 이미 경기장에 있거나, 바로 직전에 패해서 경기장을 떠난 팀이라면 그 팀은 건너뛰고 순환 순서의 다음 팀이 들어온다.

모든 두 팀의 맞대결 결과는 미리 정해져 있다. 같은 두 팀이 경기하면 언제나 같은 팀이 이긴다.

각 팀이 총 몇 경기를 하는지 구하여라.

첫 줄에 정수 N과 K가 주어진다. (3 <= N <= 1000, 0 <= K <= 10^14)

다음 N개의 줄에는 0과 1로만 이루어진 길이 N의 문자열이 주어진다. 이 문자열들은 N x N 승패 행렬 A를 나타낸다.

Aij가 1이면 i번 팀이 j번 팀을 항상 이기고, Aij가 0이면 j번 팀이 i번 팀을 항상 이긴다. 서로 다른 모든 i, j에 대해 Aij와 Aji는 서로 다르다.

한 줄에 N개의 정수를 공백으로 구분해 출력한다. i번째 정수는 i번 팀이 하는 총 경기 수이다.

정답은 signed 64-bit integer 범위에 들어가므로 해당 범위를 담을 수 있는 정수형을 사용한다.