D. Дзи тэмдэгт мөрүүдэд дуртай

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

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

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

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

Дзи тэмдэгт мөрүүдэд дуртай бөгөөд тэдгээрийг цуглуулах нь түүнд таалагддаг.

Хятадад олон хүмүүс нэрнийхээ эхний үсгийг агуулсан тэмдэгт мөр ашиглах дуртай байдаг, жишээлбэл: $xyz$, $jcvb$, $dzy$, $dyh$.

Нэг уда Дзи $s$ азтай тэмдэгт мөрийг олсон байна. Энэ мэдээг дуулаад түүний олон хос сайн найзууд ирсэн. $i$-р хосын эхний гишүүний нэр нь $a_{i}$, хоёр дахь гишүүний нэр нь $b_{i}$. Азтай тэмдэгт мөрөнд тэдний хоёулангийнх нь нэрийг агуулсан дэд тэмдэгт мөр байгаа болов уу гэж хос бүр бодсон. Тиймээс тэд хамгийн бага урттай дэд тэмдэгт мөр олохыг хүссэн ба энэ нь тэдэнд аз авчирч мөн үүрдийн нөхөрлөлийг бий болгоно.

Хос бүрийн $a_{i}$ ба $b_{i}$-г хоёуланг нь агуулсан $s$ тэмдэгт мөрийн хамгийн бага урттай дэд тэмдэгт мөрийг олоход Дзид туслана уу, эсвэл дэд тэмдэгт мөр байхгүй байна гэж мэдэгдэнэ үү.

Ямар нэг $l, r (1 ≤ l ≤ r ≤ |s|)$ бүхэл тоонуудын хувьд $s$-н дэд тэмдэгт мөр нь $s_{l}s_{l + 1}... s_{r}$ байна. Ийм дэд тэмдэгт мөрийн урт нь $(r - l + 1)$ байна.

$p$ тэмдэгт мөр нь өөр $q$ тэмдэгт мөрийг агуулсан бол $p$-н дэд тэмдэгт мөр нь $q$-тэй тэнцүү.

Оролт

Эхний мөр нь $s$ $(1 ≤ |s| ≤ 50000)$ тэмдэгт мөрийг агуулна.

Хоёр дахь мөр нь хоосон биш $q$ $(0 ≤ q ≤ 100000)$ бүхэл тоог агуулна. Энэ нь хосуудын тоо юм. Дараагийн $q$ мөрүүдэд хосуудын тодорхойлолтууд байх ба мөр бүр нь зайгаар тусгаарлагдсан $a_{i}$, $b_{i}$ $(1 ≤ |a_{i}|, |b_{i}| ≤ 4)$ бүхэл тоонуудыг агуулна.

Бүх тэмдэгт мөрүүд Англи жижиг үсгүүдээс бүтсэн байна.

Гаралт

Хос бүрт ямар нэг бүхэл тоо агуулсан мөр хэвлэнэ. Энэ нь шаардсан дэд тэмдэгт мөрийн хамгийн бага урт юм. Хэрвээ ийм дэд тэмдэгт мөр байхгүй бол $-1$ гэж хэвлэнэ.

Орчуулсан: Даариймаа

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

Оролт
xudyhduxyz
3
xyz xyz
dyh xyz
dzy xyz
Гаралт
3
8
-1
Оролт
abcabd
3
a c
ab abc
ab d
Гаралт
2
3
3
Оролт
baabcabaaa
2
abca baa
aa aba
Гаралт
6
4

Тэмдэглэл

Эхний жишээний хамгийн богино дэд тэмдэгт мөр: $xyz$, $dyhduxyz$.

Хоёр дахь жишээний хамгийн богино дэд тэмдэгт мөр: $ca$, $abc$ $abd$.

Гурав дахь жишээний хамгийн богино дэд тэмдэгт мөр: $baabca$ $abaa$.

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