Write a program that,
given n different words s_{1}, …, s_{n}
and a number p,
prints all the ways to share the words between p subsets.

Input

Input consists of a natural number n > 0,
followed by s_{1}, …, s_{n},
followed by a natural number p > 0.

Output

Print all the ways to share the words between p subsets. The elements of each set must appear in the same order than in the input. Print an empty line after each partition.

Observation

Strictly speaking, a partition cannot have empty subsets, but we forget about that restriction in this exercise.

You can print the solutions to this exercise in any order.

Public test cases

**Input**

2 hello bye 2

**Output**

subset 1: {hello,bye} subset 2: {} subset 1: {hello} subset 2: {bye} subset 1: {bye} subset 2: {hello} subset 1: {} subset 2: {hello,bye}

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++ Python
- User solutions
- C++ Python