만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

특이한 수열

시간 제한2초메모리 제한512 MB

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

쉬움10점 중 3점

유형
수학, 정수론, 그리디, 구현
정답자
아직 제출이 없습니다

문제

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

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

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

입력

첫째 줄에 nn과 kk가 공백으로 구분되어 주어진다. (1≤n≤1051 \le n \le 10^5, 0≤k≤n0 \le k \le n)

출력

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

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

  • 1≤i≤m−11 \le i \le m - 1이면 Ai=i+1A_i = i + 1
  • Am=1A_m = 1
  • m+1≤i≤nm + 1 \le i \le n이면 Ai=iA_i = i

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

예제2

  1. 예제 1

    입력
    1 1
    
    예상 출력
    Impossible
    
  2. 예제 2

    입력
    4 2
    
    예상 출력
    2 1 3 4