На другом краю галактики находится планета Нгонапхакаде. Именно на этой планете Умфунди работает в лучшей школе страны, где преподает язык Йендаво. Как и на Земле, на Нгонапхакаде дети очень любят придумывать новые слова, которые никто вокруг не понимает. Недавно от других учителей Умфунди узнала, что среди её учеников набирает популярность слово $$$W$$$. Умфунди стало интересно, насколько часто молодёжь использует данное слово, поэтому она решила провести эксперимент.
Пару дней назад её ученики писали сочинение, поэтому теперь у Умфунди есть целых $$$N$$$ строк текста на Йендаво, в которых она и намерена искать заветное слово.
Однако она понимает, что слово может быть спрятано, поэтому она решила искать не точные совпадения, а с точностью до циклического сдвига каждой буквы искомого слова вперёд на одинаковое количество позиций в алфавите (также известного как 'шифр Цезаря'). Например, если бы на их планете использовали русский алфавит, то для искомого слова 'абв' в тексте 'юяабгде' она бы посчитала слова 'где' (сдвиг на 3) и 'юяа' (сдвиг на 31).
Помогите Умфунди для каждой работы найти все позиции, начиная с которых может прятаться интересующее её слово.
В первой строке вводится единственное целое число $$$C$$$ ($$$1 \le C \le 10^6$$$) — размер алфавита в языке Йендаво. Так как настолько экзотических символов нет даже в Unicode, буквы этого языка были пронумерованы числами от 1 до $$$C$$$ в порядке своего нахождения в алфавите Йендаво.
Во второй строке вводится искомое слово $$$W$$$. Слово представляет непустую последовательность чисел от 1 до $$$C$$$, которая заканчивается нулём. Ноль не входит в слово. Длина слова не превосходит $$$5\cdot10^5$$$ символов.
В третьей строке вводится единственное целое число $$$N$$$ ($$$1 \le N \le 10^5$$$) — количество сочинений.
В последующих $$$N$$$ строках вводятся тексты сочинений в том же формате, что и искомое слово. Гарантируется, что суммарная длина сочинений не превосходит $$$10^6$$$ символов.
Для каждого сочинения в $$$i$$$-й строке выведите в порядке возрастания позиции, начиная с которых искомое слово может прятаться в этом сочинении. Символы в строке нумеруются с 1. В конце каждой строки выведите 0.
41 2 1 022 3 4 3 4 2 3 2 2 04 1 4 2 4 1 4 0
2 6 0 1 5 0
Объём входных данных в данной задаче велик, поэтому при написании решения настоятельно рекомендуется использовать оптимизации ввода/вывода.
