На окраине империи инков находится селение, жители которого не только охраняют границы империи, но и ведут активную торговлю с соседними племенами. В один погожий день наместник Манко получает зашифрованное сообщение из Куско, в котором предписывалось что-то сделать. Для того чтобы понять, что требуется, необходимо расшифровать сообщение с помощью ключа, который меняется каждую неделю.
Как исходное, так и закодированное сообщение состоит из 26 инкских букв, сплетённых в кипу (система инкского письма из узелков и разноцветных нитей), которые для вашего удобства представлены в виде строчных букв латинского алфавита.
Еженедельный ключ состоит из правила замены букв в алфавите, правила перестановки букв и номера первой буквы сообщения. По правилу замены букв в алфавите каждая буква исходного сообщения заменяется новой (возможно, такой же), причём одинаковые буквы исходного сообщения заменяются на одинаковые, а разные — на разные. Затем буквы промежуточного сообщения перемешивают по правилу перестановки букв, то есть переставляют буквы в сообщении местами. Последний этап кодирования состоит в дописывании в начало и в конец сообщения случайных букв так, чтобы закодированное сообщение начиналось с номера первой буквы сообщения.
Как назло, именно в эту неделю в поселение не пришло сообщение с ключом, поэтому Манко попросил Вас помочь ему расшифровать это сообщение. Ему известно, что это может быть один из $$$N$$$ шаблонных приказов, поэтому он просит Вас проверить каждый из них и для каждого шаблонного приказа сообщить все возможные номера первой буквы сообщения, после чего он сам примет решение, какое из сообщений наиболее вероятно пытались передать.
В первой строке вводится строка $$$S$$$ ($$$|S| \le 10^5$$$) — исходное закодированное послание, состоящее из строчных латинских букв.
Во второй строке вводится одно целое число $$$N$$$ ($$$1 \le N \le 1\,000$$$) — количество шаблонных приказов.
В следующих $$$N$$$ строках вводится по одной строке $$$t_i$$$ ($$$\sum |t_i| \le 10^5$$$) — сами шаблонные приказы.
Для каждого шаблонного приказа в порядке, в котором они заданы во входных данных, необходимо вывести две строки: в первой строке выводится количество номеров первой буквы сообщения, а во второй — сами номера в порядке возрастания. Гарантируется, что суммарное количество номеров первой буквы сообщения не превосходит $$$6\cdot10^6$$$.
abcdedcbc2helloworld
3 2 4 5 1 1
Пояснение к первому шаблонному приказу: 'hello'$$$\rightarrow$$$'ceddb'$$$\rightarrow$$$'bcded'$$$\rightarrow$$$'abcdedcbc'; 'hello'$$$\rightarrow$$$'ebddc'$$$\rightarrow$$$'dedcb'$$$\rightarrow$$$'abcdedcbc'; 'hello'$$$\rightarrow$$$'edccb'$$$\rightarrow$$$'edcbc'$$$\rightarrow$$$'abcdedcbc'.
Пояснения ко второму шаблонному приказу: 'world'$$$\rightarrow$$$'abcde'$$$\rightarrow$$$'abcde'$$$\rightarrow$$$'abcdedcbc'.
