Приспів
Ви раптом згадали частину приспіву пісні. Вам цікаво, у якій пісні з вашого списку з n текстів пісень вона може бути.
Вхідні дані
Вхідні дані складаються з двох частин.
Перша стрічка першої частини містить ціле число n (1 ≤ n ≤ 15), що вказує на кількість пісень у вашій базі даних. Далі йдуть n рядків, кожен з яких містить лише малі літери алфавіту [a..z].
Кожен рядок є повним текстом пісні без пробілів, ком, крапок та будь-яких інших символів, окрім малих літер. Ми спростили формат введення, щоб уникнути зайвих помилок.
Ми використовуємо реальні пісні в тестових даних, тому довжина найдовшої пісні у списку менша за 1500 символів.
Друга частина вхідних даних починається з іншого цілого числа q (1 ≤ q ≤ 20), що позначає кількість запитів. Потім йдуть q коротких рядків, кожен з яких містить лише малі літери алфавіту. Кожен рядок запиту є частиною тексту пісні, але не обов'язково з приспіву.
Приспів пісні визначається як "найдовший підрядок у тексті пісні, який з'являється більше одного разу".
Вихідні дані
Для кожного рядка запиту виведіть список індексів пісень, які містять цей рядок запиту у своєму приспіві в одному рядку. Рядок запиту вважається знайденим у приспіві, якщо він є підрядком приспіву. Якщо знайдено більше однієї пісні, розділіть їхні індекси пробілом.
Примітка: В кінці виводу не повинно бути пробілу, а нумерація пісень починається з 0. Якщо жодна пісня не містить такого приспіву, виведіть "-1" (без лапок).
Ми гарантуємо, що вивід є унікальним.
Приклади
Примітка
Щоб перевірити, чи правильно ви розумієте "приспів", ось приспіви (без лапок) чотирьох пісень у прикладі вхідних даних згідно з нашим визначенням приспіву.
Пісня 0, "thisisthechorus"
Пісня 1, "chorusishere"
Пісня 2, "chorus"
Пісня 3, "againitwasdestinysgameforwhenlovefinallycameonirushedinlineonlytofindthatyouweregone"
Пісні 0, 1 та 2 є вигаданими, щоб допомогти вам зрозуміти цю задачу.
Пісня 3 є реальною піснею під назвою "Beautiful Girl", виконаною філіппінцем "Jose Mari Chan". Це пісня, яка надихнула на цю задачу.