Задача про перестановку

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

요약

n이 최대 9이고 k가 주어질 때, 1과 2가 서로 이웃하지 않는 순열을 사전순으로 나열했을 때 k번째 순열을 출력합니다.

난이도: 쉬움10점 중 3점
유형: 조합론, 완전 탐색, 시뮬레이션, 배열
정답자: 아직 제출이 없습니다

문제

Перестановкой чисел от 1 до $n$ называется последовательность $p\_1$ , \ldots, $p\_n$ , в которую каждое из указанных чисел входит ровно один раз.

Перестановка $P=p\_1 p\_2 \ldots p\_n$ идет в лексикографическом порядке раньше перестановки $Q = q\_1 q\_2 \ldots q\_n$ , если для некоторого $k$ и для всех $1 \le t \le k$ верно $p\_t = q\_t$ и $p\_{k+1} < q\_{k+1}$ .

Рассмотрим все перестановки чисел от 1 до $n$ , в которых числа $1$ и $2$ стоят не на соседних позициях. Упорядочим их в лексикографическом порядке. Ваша задача --- найти перестановку, которая идет $k$ -ой в этом порядке.

입력

В первой строке входного файла задано два натуральных числа $n$ и $k$ ( $1 \le n \le 9$ , $1 \le k \le n!$ ). Гарантируется, что перестановка c таким номером существует.

출력

В выходной файл выведите ответ на задачу.

예제2

예제 1
입력
```
3 1
```
예상 출력
```
1 3 2
```
예제 2
입력
```
4 6
```
예상 출력
```
2 3 4 1
```