16159번 - 전광판의 숫자

신형이네 학교 식당 앞에는 서로 다른 N개의 숫자가 적혀 있고, 세로 7칸, 가로 6 x N칸으로 이루어진 직사각형 모양의 전광판이 있다. 이 전광판의 각 칸에는 전구가 하나씩 들어 있으며, 세로 7칸, 가로 6칸 크기의 전구들을 이용해서 숫자를 표현한다. 아래 그림은 0부터 9까지의 숫자가 순서대로 적혀 있는 전광판의 모습이다. 검정색 칸은 켜져 있는 전구, 비어있는 칸은 꺼져있는 전구를 의미하며, 같은 숫자를 표현하는 다른 방법은 없다고 가정한다.

전광판에 적힌 숫자들을 앞에서부터 순서대로 읽었을 때 나오는 순열을 P라고 하자. 신형이는 문득 순열 P의 원소의 순서를 바꿔서 얻을 수 있는 순열 중 사전순으로 P 다음에 오는 순열이 어떤 것일지 궁금했고, 또 그 순열이 표현된 전광판은 어떤 모습일 지 알고 싶었다.

예를 들어, 위 그림에 적힌 숫자들을 순서대로 읽으면 {1, 4, 2}가 되고. 이 숫자들의 순서를 바꿔서 만들 수 있는 순열을 사전순으로 나열하면 아래와 같다.

{1, 2, 4}, {1, 4, 2}, {2, 1, 4}, {2, 4, 1}, {4, 1, 2}, {4, 2, 1}

이 중, 사전순으로 {1, 4, 2} 다음에 오는 순열은 {2, 1, 4}이므로 신형이가 궁금해하는 순열은 {2, 1, 4}가 된다. 그리고 이를 전광판으로 표현한 모습은 위와 같다. 학교 식당 앞 전광판의 모습이 주어졌을 때, 신형이가 궁금해하는 순열을 표현한 전광판의 모습을 출력하는 프로그램을 작성하시오.

N(1 ≤ N ≤ 10)개의 숫자를 표현하고 있는 세로 7칸, 가로 6 x N칸 크기의 전광판의 모습이 7줄에 걸쳐 주어진다. 여기서 1은 켜져 있는 전구, 0은 꺼져 있는 전구를 의미한다.

학교 식당 앞 전광판의 모습이 주어졌을 때, 전광판 숫자들의 순서를 바꿔서 만들 수 있는 순열 중 사전순으로 다음에 있는 순열을 전광판에 표현한 모습을 출력하라. 만약, 사전순으로 다음에 있는 순열이 없다면 "The End"를 출력하라.