Practice Backtracking and DFS with the exercise "Number Partition"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Backtracking
DFS
Recursion
Number theory

Statement

Goal

In number theory and combinatorics, an integer partition of a positive integer n is a way of expressing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition.

Write a program outputting all integer partitions of n in reverse lexicographic order. Each partition must satisfy the following conditions:

a1 + a2 + ... + ak = n
a1 ≥ a2 ≥ ... ≥ ak > 0

Output all integer partitions of n in reverse lexicographic order. The integers within each partition should be separated by spaces.

Input

An integer n.

Output

Multiple lines: each containing one partition.

Constraints

1 ≤ n ≤ 9

Example

Input

Output

Solve it

A higher resolution is required to access the IDE