Partitions P70756

Statement

Write a program that, given $n$ different words $s_1, \dots, 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, \dots, 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.

Information about the checker

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