Карточки

시간 제한2초메모리 제한1024 MB

요약

목표 단어 t와 서로 접미사 관계가 아닌 카드들이 주어질 때, t를 부분 문자열로 포함하는 가장 짧은 카드 배열을 찾는다.

난이도: 어려움10점 중 8점
유형: 문자열, 동적 계획법, 문자열 매칭, 트라이
정답자: 아직 제출이 없습니다

문제

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

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

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

입력

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

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

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

출력

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

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

예제3

예제 1
입력
```
abacaba
5
zyx
a
aba
b
c
```
예상 출력
```
3
abacaba
```

예제 2

입력

torneo
3
qwertorn
neco
eopass

예상 출력

2
qwertorneopass

예제 3

입력

torneo
3
qwerty
neco
eopass

예상 출력

No solution