분배 Batch 컴파일 명령

0 이상 2^N-1 이하의 모든 정수가 하나씩 있다. 또한 정수들을 담을 수 있는 상자가 2^K개 있으며, 각 상자에는 1부터 2^K까지의 자연수 번호가 차례대로 붙어 있다.

나는 가지고 있는 2^N개의 정수들을 2^K개의 상자에 넣으려고 한다. 나는 정수들이 골고루 분배되기를 원하므로, 각 상자에 들어 있는 정수의 개수는 서로 같아야 한다. 따라서 분배 결과 2^K개의 상자 각각에는 2^N-K개의 서로 다른 정수들이 들어 있게 된다. 그런데 안타깝게도 나는 완벽주의자이기 때문에, 모든 상자에 대해 그 상자 안에 들어 있는 모든 수를 각각 이진수로 나타냈을 때 1의 개수의 합이 서로 같도록 분배해야 한다.

입력

첫 번째 줄에 두 개의 자연수 N, K (1 ≤ K < N ≤ 16)이 공백을 사이로 두고 주어진다.

출력

2^K개의 줄을 출력한다. 이 중 i(1 ≤ i ≤ 2^K)번째 줄에는 i번 상자에 들어 있는 정수 2^N-K개를 공백 하나를 사이로 두고 출력한다.

전체 출력에서 같은 수가 여러 번 나오면 안 되고, 각 상자마다 들어 있는 모든 수를 이진수로 나타냈을 때 나타난 1의 개수의 합이 모든 상자에 대해 동일해야 한다.

부분문제

이 문제는 부분문제가 없는 것과 같다.

입출력 예제

• 1번 상자: 0 = 0₍₂₎, 3 = 11₍₂₎ 이므로, 1은 총 2개
• 2번 상자: 1 = 1₍₂₎, 2 = 10₍₂₎ 이므로, 1은 총 2개

상자에 있는 수들이 중복되지 않고, 각 상자마다 그 안에 들어 있는 수를 이진수로 나타냈을 때 나타나는 1의 개수의 합이 2로 서로 같으므로, 이 분배는 완벽주의자인 나에게도 만족스러운 분배인 것이다.