벽

Tomorrow Programming School은 입구 홀 앞쪽 벽을 기본 셀룰러 오토마타의 출력 패턴으로 꾸밀 계획이다. 설계팀은 여러 오토마타의 출력을 살펴본 뒤 가장 마음에 드는 것을 고른다.

이 문제에서는 오토마타의 출력을 그대로 재현하는 프로그램을 작성한다.

기본 셀룰러 오토마타는 셀이 한 줄로 늘어선 시스템과 규칙으로 이루어진다. 각 셀은 0 또는 1 상태를 가진다. 셀 전체의 상태를 순서대로 나열한 것을 한 세대라고 한다.

오토마타는 주기를 반복한다. 한 주기에서는 현재 세대를 입력으로 받아 모든 셀에 규칙을 적용하고 새 세대를 계산한다. 주기가 끝나면 새 세대가 현재 세대를 대신한다. 이 주기는 원하는 만큼 반복할 수 있다.

가장 왼쪽과 가장 오른쪽 셀에는 상태가 항상 0인 사용하지 않는 셀이 이웃해 있다고 가정한다. 덕분에 모든 셀에 같은 방식으로 규칙을 적용할 수 있다. 사용하지 않는 셀은 입력과 출력에 나타나지 않는다.

셀 C의 새 상태는 현재 세대에서 C와 양쪽 이웃 셀의 상태, 그리고 규칙에 따라 정해진다. 세 셀의 상태 조합은 $2^3 = 8$가지이며, $S = (111, 110, 101, 100, 011, 010, 001, 000)$ 순서로 나열한다. 가운데 자리는 C의 상태이고, 첫째 자리와 셋째 자리는 각각 왼쪽과 오른쪽 이웃 셀의 상태다.

규칙은 S의 여덟 조합 각각에 0 또는 1 비트를 대응시킨 8비트 벡터다. S의 순서대로 비트를 나열한 이 벡터를 10진수로 표현한 것이 규칙 번호다. S 자체는 규칙 번호에 포함되지 않는다.

C에 규칙을 적용하려면 현재 세대에서 C와 양쪽 이웃의 상태에 맞는 조합을 S에서 찾는다. 그 조합에 대응하는 비트가 C의 다음 상태가 된다.

규칙 번호는 0부터 255까지이므로 오토마타는 $2^8 = 256$가지다.

첫 줄에는 10진수로 표현한 규칙 번호 R과 세대 수 K가 주어진다 (0 ≤ R ≤ 255, 1 ≤ K ≤ 200). 둘째 줄에는 첫 번째 세대가 주어진다. .은 상태 0, X는 상태 1을 뜻한다. 세대는 공백 없이 하나의 문자열로 주어지며, 셀의 개수는 1 이상 250 이하다.

첫 번째 세대 다음부터 K개의 세대를 출력한다. 각 세대는 입력의 첫 번째 세대와 같은 형식으로 한 줄에 하나씩 출력한다. 빈 줄은 출력하지 않는다.