C. Хачирхалтай эрэмбэлэлт

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

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

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

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

Та хэдэн тусгай дараалал мэдэх вэ? Өсч буй дараалал, буурч буй дараалал, өсч буй уртын дараалал, өсч буй туйлын өнцгийн дараалал... $d$-эрэмбэлэлт гэсэн өөр нэгэн тусгай дарааллыг авч үзье. Энэхүү эрэмбэлэлтийг дор хаяж $d$ урттай тэмдэгт мөрөн дээр хэрэглэдэг (энд $d$ нь эерэг бүхэл тоо). Тэмдэгт мөрийн тэмдэгтүүд дараах байдлаар эрэмбэлэгддэг: Эхлээд анхны тэмдэгт мөрний бүх 0 байрлалтай тэмдэгтүүд, дараа нь 1 байрлалтай тэмдэгтүүд, дараа нь 2 байрлалтай тэмдэгтүүд гэх мэт үргэлжилнэ. Эцэст нь анхны тэмдэгт мөрний $(d - 1)$ байрлалтай тэмдэгтүүд байрлана. $i$ байрлалтай тэмдэгтүүд гэдэг нь байрлалынх нь дугаарыг $d$-д хуваахад гарах үлдэгдэл нь $i$ байвал энэ тэмдэгтийг $i$ байрлалтай тэмдэгт гэнэ. Хэрвээ байрлалууд нь $d$-д хуваагдаад адил үлдэгдэл өгдөг 2 тэмдэгт байвал эрэмбэлэлтийн дараа энэ 2 тэмдэгтийн анхны харьцангуй байрлал нь өөрчлөгдөхгүй. Тэмдэгт мөр нь тэг-индексжүүлсэн. Жишээ нь тэмдэгт мөр '$qwerty$'-ийн хувьд:

Үүний 1-эрэмбэлэлт нь '$qwerty$' (бүх тэмдэгтүүд нь 0 байрлалтай).

Үүний 2-эрэмбэлэлт нь '$qetwry$' ('$q$', '$e$', '$t$' нь 0 байрлалтай, '$w$', '$r$', '$y$' нь 1 байрлалтай).

Үүний 3-эрэмбэлэлт нь '$qrwtey$' ('$q$', '$r$' нь 0 байралтай, '$w$', '$t$' нь 1 байрлалтай, '$e$', '$y$' нь 2 байрлалтай).

Үүний 4-эрэмбэлэлт нь '$qtwyer$'.

Үүний 5-эрэмбэлэлт нь '$qywert$'.

Танд $n$ урттай тэмдэгт мөр $S$ өгөгдөх бөгөөд $m$ ширхэг энэ тэмдэгт мөрийн байрыг солих буюу холих үйлдэл өгөгдөнө. Холилт болгон нь 2 бүхэл тоо $k$, $d$-оор илэрхийлэгддэг бөгөөд тэмдэгт мөр $S$-ийг дараах байдлаар өөрчилдөг. $i$ болгоны хувьд $0$-оос $n - k$ хүртэл өсөх дарааллаар, $d$-эрэмбэлэлтийг дэд тэмдэгт мөр $S[i..i + k - 1]$-нд хэрэглэнэ. Энд $S[a..b]$ гэдэг нь $a$ тэмдэгтийн байрлалаас $b$ тэмдэгтийн байрлал хүртэл тэмдэгтүүдээс бүтсэн дэд тэмдэгт мөрийг илтгэнэ (Энд 2 хязгаар орно).

Холилт болгоны дараах тэмдэгт мөр $S$-ийг хэвлэнэ үү.

Оролт

Эхний мөрөнд $n$ урттай хоосон бус тэмдэгт мөр $S$ өгөгдөнө. Энэ тэмдэгт мөр нь том, жижиг Англи цагаан толгой болон 0-оос 9 хүртэлх тооноос бүтсэн байна.

2 дахь мөрөнд холилтын тоо болох бүхэл тоо $m$ өгөгдөнө ($1 ≤ m*n ≤ 10^{6}$).

Дараагийн $m$ ширхэг мөрний мөр болгонд холилт болгоны тайлбар болох 2 бүхэл тоонууд $k$, $d$ ($1 ≤ d ≤ k ≤ n$) өгөгдөнө.

Гаралт

Холилт болгоны дараах тэмдэгт мөр $S$-ийг хэвлэнэ үү.

Орчуулсан: Энхлут

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

Оролт
qwerty
3
4 2
6 3
5 2
Гаралт
qertwy
qtewry
qetyrw

Тэмдэглэл

Жишээний дэлгэрэнгүй тайлбар. Эхний холилт нь $k = 4$, $d = 2$. Тиймээс та 2-эрэмбэлэлтийг зүүнээс эхлэн баруун уруу 4 урттай тэмдэгт мөр болгонд хэрэглэх юм. Тэмдэгт мөр нь дараах байдлаар өөрчлөгдөнө:

$qwerty$  ->  $qewrty$  ->  $qerwty$  ->  $qertwy$

Тиймээс $S$ тэмдэгт мөр нь эхний холилтын дараа '$qertwy$' болох юм.

2 дахь холилт нь $k = 6$, $d = 3$. Иймээс бүхэл тэмдэгт мөр $S$-нд 3-эрэмбэлэлт хэрэглэх юм:

$qertwy$  ->  $qtewry$

3 дахь холилт нь $k = 5$, $d = 2$.

$qtewry$ ->  $qertwy$  ->  $qetyrw$

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