두 개의 문
시간 제한1초메모리 제한1024 MB
고른 스위치로 문들을 뒤집은 뒤 통로를 지날 때 이동하는 연수가 정확히 i가 되도록, -n부터 n까지 각 i에 대해 누를 스위치 조합을 구한다.
문제
도도는 시공의 폭풍으로 빨려 들어간 에아를 찾으러 나섰습니다. 에아가 지금으로부터 미래로 (-n)년과 n년 사이에 있다는 정보만 알고서 타임머신을 찾아 나선 도도는, 검은 마법사로부터 신기한 문을 알아냈습니다.
이 문은 앞면과 뒷면이 있으며, 앞면이 뒷면보다 항상 1년 미래입니다. 즉, 문을 앞에서 뒤로 들어가면 1년 과거로 갈 수 있고, 뒤에서 앞으로 들어가면 1년 미래로 갈 수 있습니다.
악마 같은 검은 마법사는 이 문을 그냥 줄 수는 없다면서, n개의 문을 이어붙인 통로를 주겠다고 했습니다. 도도는 오랜 연구 끝에 특정 문의 조합을 180도 돌릴 수 있는 m개의 스위치를 설치했습니다. 이제 이 스위치를 사용하여 에아를 구하러 갑시다!
입력
첫째 줄에 n(1 ≤ n ≤ 100)과 m(1 ≤ m ≤ 20)이 주어집니다.
둘째 줄에 길이 n의 0과 1로만 구성된 문자열이 주어집니다. 모든 1 ≤ j ≤ n에 대해, 이 문자열의 j번째 문자는 j번째 문의 초기 상태를 나타내며, 0이라면 문의 앞면, 1이라면 문의 뒷면이 도도를 향하고 있음을 나타냅니다.
셋째 줄부터 (m+2)번째 줄까지 길이 n의 0과 1로만 구성된 문자열 m개가 주어집니다. 모든 1 ≤ i ≤ m, 1 ≤ j ≤ n에 대해 (i+2)번째 줄의 j번째 문자는 i번 스위치가 j번 문을 180도 돌리는지 여부를 나타내며, 0이라면 돌리지 않음을, 1이라면 돌림을 의미합니다.
출력
총 (2n+1)개의 줄을 출력합니다. 모든 -n ≤ i ≤ n에 대해, (i+n+1)번째 줄에는 미래로 i년을 가려고 할 때에 해당하는 답을 출력합니다.
각 줄에는, 정답이 존재한다면 눌러야 하는 스위치의 개수 k(0 ≤ k ≤ m)와 스위치 번호를 공백을 사이에 두고 출력합니다. 정답이 존재하지 않으면 -1을 출력합니다.
눌러야 하는 스위치의 조합이 여러 가지라면 아무거나 하나를 출력합니다.
힌트
빨간색을 문이 앞면을 보고 있는 상태, 파란색을 뒷면을 보고 있는 상태라 했을 때, 예제의 초기 상태는 위쪽 통로와 같습니다. 이 상태로 통로를 통과하면 (-3)년 미래, 즉 3년 과거로 가게 됩니다. 여기서 2번 스위치를 누르면 아래 통로와 같게 됩니다. 이 상태로 통로를 통과하면 1년 미래로 가게 됩니다.