Expect some short downtimes and small glitches during the first week of February.

Permutations with repetition P12603

Statement

Write a program that, given $n$ different words $s_1, \dots, s_n$ , prints all the permutations with repetitions that can be made with the words.

Input

Input consists of a natural number $n > 0$ , followed by $s_1, \dots, s_n$ .

Output

Print all the permutations with repetitions that can be made with $s_1, \dots, s_n$ .

Information about the checker

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

Public test cases

Input

3
hola adeu hi

Output

(hola,hola,hola)
(hola,hola,adeu)
(hola,hola,hi)
(hola,adeu,hola)
(hola,adeu,adeu)
(hola,adeu,hi)
(hola,hi,hola)
(hola,hi,adeu)
(hola,hi,hi)
(adeu,hola,hola)
(adeu,hola,adeu)
(adeu,hola,hi)
(adeu,adeu,hola)
(adeu,adeu,adeu)
(adeu,adeu,hi)
(adeu,hi,hola)
(adeu,hi,adeu)
(adeu,hi,hi)
(hi,hola,hola)
(hi,hola,adeu)
(hi,hola,hi)
(hi,adeu,hola)
(hi,adeu,adeu)
(hi,adeu,hi)
(hi,hi,hola)
(hi,hi,adeu)
(hi,hi,hi)

Information

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