시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 25 8 5 26.316%

문제

  동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 원숭이는 자신의 생각을 사람들에게 전해주고 싶었지만 안타깝게도 사람들은 그의 언어를 이해하지 못했다. 그래서 그는 괴로웠다.

  사람들에게 자신의 생각을 전하기 위해 그 원숭이는 새로운 언어 전달법을 개발하였다. 그것은 바로 드럼통을 이용한 것이다. 원숭이는 0부터 K-1까지의 숫자를 이해할 수 있다. 그래서 드럼통에 K^M개의 칸을 만들고 그곳에 0에서 K-1사이의 수를 쓴다. 그리고 드럼통을 한 칸씩 돌리면서 원숭이가 한 번에 읽을 수 있는 M개의 칸에 적힌 수들을 메시지로 전달하면 되는 것이다. 다음 그림을 보자.
 

  다음 그림은 K=3, M=2 인 경우이다. 처음에 읽은 메시지는 “12” 이고, 시계방향으로 한 칸 돌리면 “22” 라는 메시지를 읽게 된다. 다시 시계방향으로 한 칸 돌리면 “20” 이라는 메시지를 읽게 된다. 그런 식으로 죽 읽어나가면 위에 나타난 드럼통을 이용해서 0부터 2사이의 수를 이용해 길이가 2인 조합의 메시지를 모두 얻을 수 있다.

  원숭이는 0부터 K-1의 수를 써서 길이가 M인 모든 메시지를 드럼통으로 표현하고 싶다. K와 M이 주어졌을 때, 드럼통을 돌려서 K^M개의 조합을 모두 얻을 수 있는 드럼통이 존재하는지, 존재하면 드럼통을 어떤 식으로 만들어야 하는지를 구하는 프로그램을 작성하시오.
 

입력

  첫째 줄에 자연수 K, M이 주어진다. K는 2이상, M은 1이상인 자연수이다. 항상 K^M≤10,000,000을 만족한다.

출력

  첫째 줄에 드럼통에 적힌 K^M개의 수를 순서대로 출력한다. 시계방향이던 반시계방향이던 아무 곳에서나 시작하여 순서대로 한 바퀴만 출력하면 된다. 답이 여러 개면 아무거나 하나만 출력한다. 드럼통을 만드는 것이 불가능할 경우 -1을 출력한다.

예제 입력

2 4

예제 출력

0 1 0 1 0 0 1 1 1 1 0 1 1 0 0 0

힌트

출처

  • 문제를 만든 사람: ntopia