D. Сэрэжа ба давталтууд

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

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

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

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

Нэгэн тэмдэглэгээ танилцуулъя:

$$[x, n] = x + x + ... + x = \sum\limits_{i=1}^{n}x$$

Энд $x$ нь тэмдэгт мөр, $n$ нь эерэг бүхэл тоо ба "+" нь тэмдэгт мөрийг араас нь залгах үйлдэл юм. Жишээлбэл $[abc, 2] = abcabc$ байна.

Хэрэв бид $t$ тэмдэгт мөрийн зарим тэмдэгтүүдийг арилгах замаар $s$ тэмдэгт мөрийг гаргаж чаддаг бол $s$-ийг $t$-ээс гардаг гэе. Жишээ нь "ab" ба "aсba" нар нь "xacbac"-аас гардаг боловч "bx" ба "aaa" нар нь гардаггүй юм.

Сэрэжад $w = [a, b]$ ба $q = [c, d]$ гэсэн хоёр тэмдэгт мөр байгаа. Тэрээр $[q, p]$ нь $w$-аас гардаг байхаар хамгийн том $p$ $(p > 0)$ тоог олохыг хүсжээ.

Оролт

Эхний мөрөнд $b$, $d$ $(1 ≤ b, d ≤ 10^{7})$ бүхэл тоонууд байна. Хоёр дахь мөрөнд $a$ тэмдэгт мөр байна. Гурав дахь мөрөнд $c$ тэмдэгт мөр байна. Өгөгдсөн тэмдэгт мөрүүд Англи цагаан толгойн жижиг үсгүүдээс тогтох ба хоосон биш байна. Мөн уртууд нь $100$-аас хэтрэхгүй.

Гаралт

Хамгийн том $p$-ийн утгыг хэвлэ. Хэрэв нөхцөлийг хангах $p$ тоо олдохгүй бол "0" гэж хэвлэ.

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

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

Оролт
10 3
abab
bab
Гаралт
3
Сэтгэгдлүүдийг ачааллаж байна...