특이한 수열

n과 k가 주어질 때 gcd(i, A_i) > 1인 위치가 정확히 k개인 순열을 찾고, 주어진 규칙으로 만든 수열을 출력한다.

쉬움3수학정수론그리디구현아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

길이가 nn인 수열 AA가 다음 두 조건을 모두 만족하면 특이한 수열이라고 한다.

  • 11 이상 nn 이하의 정수가 빠짐없이 한 번씩 등장한다. 즉 AA11부터 nn까지의 순열이다.
  • 1in1 \le i \le nii 중에서 gcd(i,Ai)>1\gcd(i, A_i) > 1을 만족하는 ii가 정확히 kk개다.

nnkk가 주어질 때 특이한 수열을 하나 구한다.

입력

첫째 줄에 nnkk가 공백으로 구분되어 주어진다. (1n1051 \le n \le 10^5, 0kn0 \le k \le n)

출력

조건을 만족하는 특이한 수열이 없으면 첫째 줄에 Impossible을 출력한다.

수열이 있으면 답이 여러 개일 수 있으므로, 아래 규칙으로 정한 수열 하나만 정답으로 인정한다. m=nkm = n - k라고 할 때 수열 AA를 다음과 같이 정한다.

  • 1im11 \le i \le m - 1이면 Ai=i+1A_i = i + 1
  • Am=1A_m = 1
  • m+1inm + 1 \le i \le n이면 Ai=iA_i = i

앞의 mm개 자리에는 2,3,,m,12, 3, \dots, m, 1이 순서대로 놓이고, 나머지 자리에는 Ai=iA_i = i가 놓인다. 이 수열 AA를 첫째 줄에 공백으로 구분해 출력한다.