C. Цикл хүсэлт

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Codeforces-н гишүүн WJMZBMR хэд хоногийн өмнө "$s$ тэмдэгт мөрөнд $x$ тэмдэгт мөр хэдэн удаа тааралдах вэ" гэх хүсэлтэнд хурдан хариулах арга сурчээ. Тэгээд тэрээр хүсэлт боловсруулалтыг илүү хүнд болгохыг хүсчээ.

Тиймээс тэрээр "$s$-ийн хичнээн дэд тэмдэгт мөр нь $x$ тэмдэгт мөртэй цикл изоморф бэ" гэсэн бодлого зохиожээ. Чамд $s$ тэмдэгт мөр болон $n$ ширхэг $x_{i}$ тэмдэгт мөрүүд өгөгдөх ба $x_{i}$ тэмдэгт мөр бүрт $s$-ийн хичнээн дэд тэмдэгт мөр нь $x_{i}$ тэмдэгт мөртэй цикл изоморф байхыг олох юм.

Хоёр тэмдэгт мөрийн нэгийг нь эргүүлэх замаар нөгөөг нь гаргаж болдог бол тэднийг хоорондоо цикл изоморф гэнэ. Энд эргүүлэх гэдгээр тэмдэгт мөрийн үргэлжилсэн угтварыг ард нь залгуулах үйлдлийг хэлнэ. Жишээлбэл "abcde" тэмдэгт мөрийг эргүүлэн "deabc" тэмдэгт мөрийг гаргаж чадна. Өөрөөр хэлбэл "abc" угтварыг аван "de"-ийн араас залгахад хангалттай юм.

Оролт

Эхний мөрөнд хоосон биш $s$ тэмдэгт мөр өгөгдөнө. $s$ тэмдэгт мөрийн урт $10^{6}$-аас хэтрэхгүй.

Хоёр дахь мөрөнд хүсэлтийн тоог илэрхийлэх $n$ ($1 ≤ n ≤ 10^{5}$) гэсэн бүхэл тоо байна. Дараагийн $n$ мөрөнд: $i$ дэх мөрөнд $i$ дэх хүсэлтийн $x_{i}$ тэмдэгт мөр байна. $x_{i}$ тэмдэгт мөрүүдийн нийт урт $10^{6}$-аас хэтрэхгүй.

Энэ бодлогон дахь тэмдэгт мөр бүр зөвхөн Англи цагаан толгойн жижиг үсгүүдээс тогтоно.

Гаралт

$x_{i}$ хүсэлт бүрт $s$-ийн хичнээн дэд тэмдэгт мөр нь $x_{i}$ тэмдэгт мөртэй цикл изоморфизм болохыг хэвлэ. Хүсэлтийн хариуг хүсэлтүүдийн өгөгдөлд буй дарааллаар хэвлэ.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
baabaabaaa
5
a
ba
baa
aabaa
aaba
Гаралт
7
5
7
3
5
Оролт
aabbaa
3
aa
aabb
abba
Гаралт
2
3
3
Сэтгэгдлүүдийг ачааллаж байна...