E. Ангарагын тэмдэгт мөрүүд

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

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

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

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

Ангарагын хүний талаар судалж байхдаа Петя Ангарагын хүмүүс үнэхээр залхуу болохыг баттай ойлгожээ. Тэд унтах дуртай ба сэрэх дургүй байв.

Нэг мөрөнд байрласан яг $n$ ширхэг нүдтэй бөгөөд эдгээр нүднүүд нь зүүнээсээ баруун хүртэл $1$-ээс $n$ хүртэл дугаарлагдсан Ангарагын хүнийг авч үзье. Ангарагын хүн унтаж байхдаа нүд болгондоо нүдний даруулга хийдэг (ингэснээр Ангарагын өглөө нь түүнийг сэрээхгүй). Даруулга бүрийн дотор талд нэгэн Латин том үсэг байв. Иймд Ангарагын хүн сэрээд бүх нүдээ нээхэд тэрээр Латин том үсгүүдээс тогтох $s$ тэмдэгт мөрийг харах юм. Уг тэмдэгт мөрийн урт нь $n$ байна.

"Динг донг!" -- сэрүүлэг унтрав. Ангарагын хүн аль хэдийн боссон боловч тэрээр өөрийнхөө ямар ч нүдийг нээгээгүй байв. Түүнд өнөөдөр хүндхэн өдөр болох юм шиг мэдрэгдсэн учраас тэрээр нүднүүдээ нээгээд ямар нэгэн сайхан зүйл харахыг хүсжээ. Ангарагын хүн зөвхөн $m$ ширхэг Ангарагын үгнүүдийг үзэсгэлэнтэй гэж үздэг. Түүнчлэн түүний хувьд өглөө эрт бүх нүдээ нээх нь үнэхээр хэцүү байх юм. Тиймээс тэрээр дараалсан нүднүүдийн үл давхцах 2 сегментийн нүднүүдээ нээнэ. Илүү дэлгэрэнгүйгээр Ангарагын хүн $a$, $b$, $c$, $d$, ($1 ≤ a ≤ b < c ≤ d ≤ n$) гэсэн 4 тоо сонгох бөгөөд $a ≤ i ≤ b$ эсвэл $c ≤ i ≤ d$ байх бүх $i$ дугаартай нүднүүдийг нээх юм. Ангарагын хүн өөрт хэрэгтэй нүднүүдээ нээсний дараа тэрээр зүүнээс баруун хүртэл бүх харагдаж буй тэмдэгтүүдийг унших ба ингэснээр тэрээр нэг үг харах юм.

Ангарагын хүн өглөө харж болох бүх ялгаатай үгнүүдийг авч үзнэ үү. Таны даалгавар бол тэдгээрийн дунд хэчнээн үзэсгэлэнтэй үг байгааг олох юм.

Оролт

Эхний мөрөнд Латин том үсгүүдээс тогтох хоосон биш $s$ тэмдэгт мөр өгөгдөнө. Тэмдэгт мөрийн урт нь $n$ ($2 ≤ n ≤ 10^{5}$) байна. 2-дахь мөрөнд үзэсгэлэнтэй үгнүүдийн тоо болох бүхэл тоо $m$ ($1 ≤ m ≤ 100$) өгөгдөнө. Дараагийн $m$ мөрөнд үзэсгэлэнтэй үгнүүд болох $p_{i}$-ууд өгөгдөх ба эдгээр нь Латин том үсгүүдээс тогтсон байх юм. Эдгээрийн уртууд нь $1$-ээс $1000$-ын хооронд байх бөгөөд бүх үзэсгэлэнтэй тэмдэгт мөрүүд нь хос хосоороо ялгаатай байна.

Гаралт

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

Орчуулсан: Баатархүү

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

Оролт
ABCBABA
2
BAAB
ABBA
Гаралт
1

Тэмдэглэл

Жишээ тестийг авч үзье. Ангарагын хүн зөвхөн 2-дахь үзэсгэлэнтэй тэмдэгт мөрийг харж чадах ба хэрэв $a = 1, b = 2$ болон $c = 4, d = 5$ гэсэн сегмент эсвэл $a = 1, b = 2$ болон $c = 6, d = 7$ гэсэн сегментийн нүднүүдээ нээвэл уг тэмдэгт мөрийг харах юм.

Сэтгэгдлүүдийг ачааллаж байна...