Задача A. Карточки

Автор:Владимир Ульянцев, Демид Кучеренко   Ограничение времени:2 сек
Входной файл:cards.in   Ограничение памяти:256 Мб
Выходной файл:cards.out  
Максимальный балл:100  

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

Вова очень тихий мальчик, он очень любит тихонько сидеть и что-нибудь делать. Недавно родители подарили Вове набор карточек, на которых написаны различные слова из латинских букв. Причем слова, написанные на карточках, выбраны таким образом, что никакое слово не является cуффиксом другого. Этот момент стал настоящим праздником для мальчика. Что он только с карточками не делал! Помимо этого, у родителей Вовы есть копировальная машина, и поэтому Вова в любой момент может делать копии любой из своих карточек.

Сегодня Вова затеял с родителями такую игру: родители называют Вове какое-то слово t, а он выкладывает на стол несколько карточек в ряд, образуя длинную строку s. При этом названное родителями слово t содержится в строке s как подстрока. Карточки накладывать друг на друга нельзя. В процессе этой игры Вова может использовать копировальную машину, то есть копировать имеющиеся у него карточки в любых количествах.

Иногда Вова решает эту задачу очень долго, и поэтому он просит вас помочь ему найти минимальное количество карточек, которое ему необходимо использовать, чтобы выполнить свою задачу.

Решения, работающие при сумме длин слов на карточках не превосходящей 1000, N ≤ 100 и длине строки t не более 1000 символов будут оцениваться из 20 баллов.

Решения, работающие при сумме длин слов на карточках не превосходящей 105, N ≤ 1000 и длине строки t не более 10000 символов будут оцениваться из 60 баллов.

Формат входного файла

В первой строке входного файла содержится слово t, названное родителями. Длина этого слова не превышает 105.

В следующей строке задано число n (1 ≤ n ≤ 105) — количество имеющихся различных карточек у Вовы. Далее следует n строк, каждая из которых содержит слово, написанное на карточке. Сумма длин всех слов на карточках не превосходит 105.

Гарантируется, что никакая карточка не содержит слово, которое является суффиксом слова, написанного на другой карточке. Как слово, названное родителями, так и слова, написанные на карточках, состоят только из строчных латинских букв.

Формат выходного файла

В первой строке выходного файла необходимо вывести единственное число k — количество использованных карточек (в том числе и полученных с помощью копировальной машины). Во второй строке необходимо вывести слово s, сложенное из k Вовиных карточек и содержащее слово t как подстроку. Если ответов несколько, выведите любой.

Если невозможно выложить карточки заданным образом, выведите в выходной файл единственную строку "No solution".

Примеры тестов

Входной файл (cards.in) Выходной файл (cards.out)
1
abacaba
4
zyx
aba
b
c
3
abacaba
2
torneo
3
qwertorn
neco
eopass
2
qwertorneopass
3
torneo
3
qwerty
neco
eopass
No solution

0.040s 0.008s 15