Concatenations (1) P69197

Statement

Write a program that, given a word $w$ and a sequence of words $s_1, \dots, s_n$ , prints all the ways to obtain $w$ by concatenating some of the given words, without changing their relative order.

Input

Input consists of a word $w$ , followed by a natural number $n > 0$ , followed by $s_1, \dots, s_n$ . The words only include lowercase letters.

Output

Print all the ways to obtain $w$ by concatenating some of the given words, without changing their relative order. If there is no solution, print a hyphen. Follow the format of the samples.

Information about the checker

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

Public test cases

Input

hola
9
ho la h o l a hola la hol

Output

hola
h+o+la
h+o+l+a
ho+la
ho+l+a
ho+la

Input

patata
5
tata ta pata tata pa

Output

Input

patata
5
pata pa ta tata tata

Output

pa+tata
pa+tata
pata+ta

Input

patata
2
pa ta

Output

Information

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