시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 172 90 78 52.349%

문제

당신에게 자연수 x0N이 주어졌다. 지금부터 당신은 이 자연수 x0N번의 '변환'을 통해 0으로 바꿀 것이다. 변환이란, 양의 정수를 이진법으로 표기하여, 1개 이상의 1을 0으로 바꾸는 작업이다. 예를 들어 9를 이진법으로 나타내면 1001(2)인데, 9는 0(0000(2)), 1(0001(2)), 또는 8(1000(2))로 변환될 수 있다. 바뀐 자릿수는 밑줄로 표기되었다. 여러분의 목표는 xi를 변환하여 xi+1를 만드는 과정을 반복해, xN을 0으로 만드는 것이다.

위 조건을 만족하는 수열 X = x0, x1, x2, ..., xN는 존재하지 않을 수도 있지만, 여러 개가 존재할 수도 있다. 만약 존재한다면, 각 수열별로 인접한 원소들의 차들의 집합 D(X) = {x0-x1, x1-x2, ..., xN-1-xN}를 정의하자. 이 집합의 원소들의 최대값과 최소값의 차이를 최소화하도록, 수열 X를 만들고자 한다. 즉, 가능한 모든 수열 Xi 중 (D(Xi)에 속한 원소의 최댓값 - D(Xi)에 속한 원소의 최솟값)이 최소가 되는 Xi를 찾고자 한다.

이상해보일 수 있는 문제지만, 당신은 대답해야 한다. 과연 1초안에 답할 수 있을까?

입력

첫 번째 줄에 변환할 자연수와 변환 횟수를 의미하는 두 자연수 x0N이 공백으로 구분되어 주어진다. (1 ≤ x0 ≤ 1016, 1 ≤ N ≤ 50)

출력

만약 조건을 만족하는 수열이 존재하지 않으면 첫 번째 줄에 -1을 출력한다.

조건을 만족하는 수열이 존재한다면, 수열의 원소를 의미하는 N개의 정수 x1, x2, ..., xN을 공백으로 구분하여 출력한다.

조건을 만족하는 수열이 여러 개 존재한다면, 아무 것이나 출력해도 좋다.

예제 입력 1

23 2

예제 출력 1

16 0

x0 = 23 = 10111(2), x1 = 16 = 10000(2), x2 = 0 = 00000(2) 로 수열을 구성하면 인접한 원소의 차의 최대값과 최소값의 차이는 16 - 7 = 9가 되며, 이보다 작게 만들 수 있는 방법은 존재하지 않는다. 또 다른 답으로는 x0 = 23, x1 = 7, x2 = 0이 있다.

예제 입력 2

48 5

예제 출력 2

-1

주어진 조건을 만족하는 x1, x2, x3, x4, x5는 존재하지 않는다.