Grilled Chicken Toppings

Hanke loves grilled chicken and has a peculiar way of seasoning it. He always uses 10 different toppings, and each topping can be used in a quantity of 1 to 3 grams. The overall deliciousness of the grilled chicken is defined as the total weight of all the toppings. In other words, if we denote the weight of the i-th topping by \(x_i\) (where \(1 \le x_i \le 3\) for \(i=1,2,\dots,10\)), then the deliciousness \(n\) is calculated as:

\(\displaystyle \sum_{i=1}^{10} x_i = n\)

Your task is: given an integer \(n\), output all possible combinations of the 10 toppings (each configuration is a sequence of 10 numbers) such that the sum of the 10 numbers equals \(n\). Each number must be either 1, 2, or 3.

Note: The output combinations should be printed in lexicographical order. For each combination, print the 10 numbers separated by a single space on one line.

inputFormat

The input consists of a single integer \(n\) (\(10 \le n \le 30\)), representing the target deliciousness level.

outputFormat

Output all valid combinations (one combination per line) where each combination consists of 10 numbers (each between 1 and 3) separated by a single space. The order of combinations must be lexicographical.

sample

10

1 1 1 1 1 1 1 1 1 1