Let's define the permutation of length *n* as an array *p* = [*p*<sub class="lower-index">1</sub>, *p*<sub class="lower-index">2</sub>, ..., *p*<sub class="lower-index">*n*</sub>] consisting of *n* distinct integers from range from 1 to *n*. We say that this permutation maps value 1 into the value *p*<sub class="lower-index">1</sub>, value 2 into the value *p*<sub class="lower-index">2</sub> and so on.

Kyota Ootori has just learned about cyclic representation of a permutation. A cycle is a sequence of numbers such that each element of this sequence is being mapped into the next element of this sequence (and the last element of the cycle is being mapped into the first element of the cycle). The cyclic representation is a representation of *p* as a collection of cycles forming *p*. For example, permutation *p* = [4, 1, 6, 2, 5, 3] has a cyclic representation that looks like (142)(36)(5) because 1 is replaced by 4, 4 is replaced by 2, 2 is replaced by 1, 3 and 6 are swapped, and 5 remains in place. 

Permutation may have several cyclic representations, so Kyoya defines the standard cyclic representation of a permutation as follows. First, reorder the elements within each cycle so the largest element is first. Then, reorder all of the cycles so they are sorted by their first element. For our example above, the standard cyclic representation of [4, 1, 6, 2, 5, 3] is (421)(5)(63).

Now, Kyoya notices that if we drop the parenthesis in the standard cyclic representation, we get another permutation! For instance, [4, 1, 6, 2, 5, 3] will become [4, 2, 1, 5, 6, 3].

Kyoya notices that some permutations don't change after applying operation described above at all. He wrote all permutations of length *n* that do not change in a list in lexicographic order. Unfortunately, his friend Tamaki Suoh lost this list. Kyoya wishes to reproduce the list and he needs your help. Given the integers *n* and *k*, print the permutation that was *k*-th on Kyoya's list.
The first line will contain two integers *n*, *k* (1 ≤ *n* ≤ 50, 1 ≤ *k* ≤ *min*{10<sup class="upper-index">18</sup>, *l*} where *l* is the length of the Kyoya's list).
#!/usr/bin/env python
# 554D_perm.py - Codeforces.com 554D Perm quiz
#
# Copyright (C) 2015 Sergey
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#       http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

"""
Given the integers n and k, print the permutation that was k-th on Kyoya'
list.
Input

The first line will contain two integers n, k (1<=n<=50,
1<=k<=min{10^18,l} where l is the length of the Kyoya's list).

Output

Print n space-separated integers, representing the permutation that is the
answer for the question.
"""

# Standard libraries
import unittest
import sys
import re

# Additional libraries


###############################################################################
# Perm Class
###############################################################################


class Perm:
    """ Perm representation """

    def __init__(self, args):
        """ Default constructor """

        self.list = args
        self.n = args[0]
        self.k = args[1]

    def extract(self, l):
        if sum(l) != len(l) or len(l) != self.n:
            raise Exception("Size of all cycles needs to be n")
        result = []
        cur = 1
        for n in l:
            tmp = []
            for i in range(n):
                tmp.append(cur)
                cur += 1
            result += reversed(tmp)
        return result

    def next(self, l):
        # modify the existing list
        result = l
        carry = 2
        for i in range(len(result)-1, -1, -1):
            if carry == 2 and result[i] != 0:
                max = len(result) - i
                if result[i] == max and max > 1:
                    for j in range(i, len(result) - 1):
                        result[j] = 1
                else:
                    result[i] -= 1
                carry = 1
            elif carry == 1:
                result[i] += 1
                carry = 0
        return result

    def calculate(self):
        """ Main calcualtion function of the class """
        result = [1 for n in range(self.n)]
        for i in range(self.k - 1):
            self.next(result)

        return str(" ".join([str(n) for n in self.extract(result)]))


###############################################################################
# Executable code
###############################################################################


def get_inputs(test_inputs=None):

    it = iter(test_inputs.split("\n")) if test_inputs else None

    def uinput():
        """ Unit-testable input function wrapper """
        if it:
            return next(it)
        else:
            return input()

    # Getting string inputs
    nums = [int(s) for s in uinput().split(" ")]

    return nums


def calculate(test_inputs=None):
    """ Base class calculate method wrapper """
    return Perm(get_inputs(test_inputs)).calculate()


###############################################################################
# Unit Tests
###############################################################################


class unitTests(unittest.TestCase):

    def test_sample_tests(self):
        """ Quiz sample tests. Add \n to separate lines """
        self.assertEqual(calculate("4 3"), "1 3 2 4")
        self.assertEqual(calculate("10 2"), "1 2 3 4 5 6 7 8 10 9")

    def test_get_inputs(self):
        """ Input string decoding testing """
        self.assertEqual(get_inputs("4 3"), [4, 3])

    def test_Perm_class__basic_functions(self):
        """ Perm class basic functions testing """

        # Constructor test
        d = Perm([3, 2])
        self.assertEqual(d.n, 3)

        # Extract permutation from the list of cycles
        self.assertEqual(d.extract([1, 2, 0]), [1, 3, 2])

        # Next cycles iterator (starting with all 1s, sum is always "n"
        d.n = 4
        self.assertEqual(d.next([1, 1, 1, 1]), [1, 1, 2, 0])
        self.assertEqual(d.next([1, 2, 1, 0]), [1, 3, 0, 0])
        # Overflow condition
        d.n = 5
        self.assertEqual(d.next([1, 4, 0, 0, 0]), [2, 1, 1, 1, 0])

if __name__ == "__main__":

    # Avoiding recursion limitaions
    sys.setrecursionlimit(100000)

    if sys.argv[-1] == "-ut":
        unittest.main(argv=[" "])

    # Print the result string
    print(calculate())
