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

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

abacaba
4
zyx
aba
b
c

3
abacaba

torneo
3
qwertorn
neco
eopass

2
qwertorneopass

torneo
3
qwerty
neco
eopass

No solution