스케줄

ICPC(Institute for Creative Product Combinations)는 서로 관련 없어 보이는 제품이나 기술을 묶는 색다르고 혁신적인 방법을 찾는다. 이런 결합은 새로운 시장을 열고 일자리를 만든다. 최근 성공 사례는 '헤어바치'다. 헤어드라이어에 히바치 그릴 덮개를 붙여, 외출 중에도 뜨거운 음식을 조리할 수 있게 만든 제품이다.

회사에는 두 명으로 이루어진 $n$개의 팀이 있다. 각 팀은 먼저 자기 팀의 제품을 연구한다. 그다음 서로 다른 팀의 구성원이 만나 제품을 결합하는 방법을 탐구한다.

팬데믹 동안 ICPC 경영진은 사무실에 동시에 $n$명을 넘는 사람이 없도록 전원의 출근 일정을 짰다. 운영이 순조로웠기 때문에, 일상이 회복된 뒤에도 이 방식을 계속 유지했다. 방식은 다음과 같다. 팀에 $1$부터 $n$까지 번호를 붙이고, $i$번 팀의 두 사람을 $(i,1)$과 $(i,2)$로 나타낸다. 매주 각 팀에서 정확히 한 명만 사무실에 출근하고, 나머지 한 명은 출근하지 않는다. $(i,1)$과 $(i,2)$는 서로를 잘 알고, 떨어져 있어도 생산적으로 협업하므로 사무실에서 만날 필요가 없다. 다만 서로 다른 팀 구성원 사이의 격리는 여전히 문제다.

서로 다른 두 팀 $i$와 $j$($i \ne j$)는 가끔 협업해야 한다. 주 수 $w$가 주어졌을 때, 고정된 팀원 $(i,a)$와 $(j,b)$가 사무실에서 만나는 주를 $w_1 < w_2 < \dots < w_k$라 하자. 이 두 사람의 격리 기간은 $\{w_1, w_2 - w_1, \dots, w_k - w_{k-1}, w+1 - w_k\}$의 최댓값이고, 한 번도 만나지 않으면 무한대다. 회사 전체의 격리 기간은 $i$, $j$, $a$, $b$의 모든 선택에 대한 격리 기간 중 최댓값이다.

$w$주 동안 회사 전체의 격리 기간을 최소화하는 주간 일정을 찾아야 한다.

정수 $n$($2 \le n \le 10^4$)과 $w$($1 \le w \le 52$)가 한 줄에 주어진다. $n$은 팀 수이고, $w$는 일정을 짤 주 수이다.

$n$개의 팀에서 달성할 수 있는 최소 격리 기간을 한 줄에 출력한다. 어떤 일정으로도 서로 다른 팀의 모든 두 사람이 반드시 만나도록 보장할 수 없으면 infinity를 출력한다. 격리 기간이 유한하면, 이를 달성하는 일정을 $w$줄로 출력한다. $j$번째 줄은 길이 $n$의 문자열이며, 숫자 1과 2만 사용한다. $i$번째 문자는 $j$주차에 $i$번 팀의 어느 구성원이 출근하는지를 나타낸다.