29428번 - Карточки 스페셜 저지다국어

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

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

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

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

В следующей строке задано число $n$ ($1 \le n \le 10^5$) --- количество имеющихся различных карточек у Вовы. Далее следует $n$ строк, каждая из которых содержит слово, написанное на карточке. Сумма длин всех слов на карточках не превосходит $10^5$.

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

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

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