For given an integer $n$, print all permutations of $\\{1, 2, ..., n\\}$ in lexicographic order.

Constraints

* $1 \leq n \leq 9$

Input

An integer $n$ is given in a line.

Output

Print each permutation in a line in order. Separate adjacency elements by a space character.

Examples

Input

2


Output

1 2
2 1


Input

3


Output

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

def permutations(n):
    """Yields all permutations of {1, 2, ... , n}

    >>> list(permutations(2))
    [[1, 2], [2, 1]]
    >>> list(permutations(3))
    [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    """

    xs = list(range(1, n+1))
    yield xs[:]

    while True:
        i = n - 1
        while i > 0 and xs[i-1] > xs[i]:
            i -= 1
        if i > 0:
            i -= 1
            j = i + 1
            while j < len(xs) and xs[j] > xs[i]:
                j += 1
            xs[i], xs[j-1] = xs[j-1], xs[i]
            xs = xs[:i+1] + list(reversed(xs[i+1:]))
            yield xs[:]
        else:
            break


def run():
    n = int(input())

    for ps in permutations(n):
        print(" ".join([str(x) for x in ps]))


if __name__ == '__main__':
    run()

