홍윤이는 새해 선물로 길이 N의 문자열을 하나 받았다.

이 문자열은 'a' 부터 알파벳 소문자의 k번째 글자까지 만을 사용해 이루어져 있다.

하지만 홍윤이는 *사전 순으로 큰 문자열을 싫어하기 때문에 문자열이 마음에 들지 않았다.

홍윤이는 다음과 같은 마법을 원하는 만큼 사용해서 문자열에서 맘에 들지 않는 글자들을 제거할 것이다.

- 마법의 표 A는 0과 1로 이루어진 k * k 행렬이다.

- 만약, A_ij = 1이고 문자열 내의 어떤 j번째 알파벳과 인접한 앞에 i번째 알파벳이 있다면 그 j번째 알파벳을 제거할 수 있다.

예를 들어 k = 3이고 마법의 표 A는

010

001

100

이라고 해보자.

만약 홍윤이가 가진 문자열이 "abacaba"라면, 뒷부분의 b (2번째 알파벳)을 제거할 수 있다.

왜냐하면 그 바로 앞에 a (1번째 알파벳)이 있고 A[1][2] = 1이기 때문이다.

제거하고 난 뒤 문자열은 "abacaa"가 된다.

우리가 할 일은 적절히 마법을 사용했을 때 만들어질 수 있는 사전 순 최소의 문자열을 알려주는 것이다.

제거 timer 3s memory 1024MB

제거 3s 1024MB