E. Харийн DNA

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

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

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

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

Профессор Бажток харийн DNA дээр туршилт явуулж байна. Тэр үүнийг давтагддаг өөрчлөлтүүдтэй зүйл гэдгийг нээсэн ба өөрчлөлт бүр ижил замаар явагдана: харийн DNA-н үргэлжилсэн дэд дараалал нь идэвхтэй болж, өөрийгөө хуулаад, хуулбар нь тэнийж анхны дэд дарааллын яг ард өөрийгөө оруулна. Идэвхтэй үргэлжилсэн дэд дарааллын тэнийсэн хуулбар гэдэг нь эхлээд уг дэд дарааллын тэгш байрлалтай элементүүдийг нэгтгээд тэгээд сондгой байрлалтай элементүүдийг нэгтгэхийг хэлнэ. Хэрвээ идэвхтэй дэд дараалал нь 11 элементээс бүрдэх ба $s_{1}s_{2}... s_{11}$ гэж дүрслэгдэж байвал түүний тэнийсэн хуулбар нь $s_{2}s_{4}s_{6}s_{8}s_{10}s_{1}s_{3}s_{5}s_{7}s_{9}s_{11}$ байна.

Жишээлбэл хэрвээ анхны дараалал "$ACTGG$" байсан ба $[2, 4]$ сегмент дээр өөрчлөлт явагдсан бол (идэвхжсэн дэд дараалал нь "$CTG$" байна) өөрлөгчдсөн DNA нь: "ACTG$TCG$G" болно. Идэвхжсэн дэд дарааллын тэнийсэн хуулбар нь хараар тэмдэглэгдсэн.

Профессор Батжок анхны DNA дараалал болон түүн дээр дарааллан хийгдэх өөрчлөлтүүдийг бичсэн ба одоо тэр таныг бүх өөрчлөлтүүдийн дараах DNA дарааллын эхний $k$ элементийг сэргээхийг хүсч байна.

Оролт

Оролтын эхний мөрөнд анхны DNA дараалал байх ба $3*10^{6}$-с ихгүй урттай ба зөвхөн "$A$", "$C$", "$T$", "$G$" тэмдэгтүүдээс тогтоно.

Хоёр дахь мөрөнд нэг бүхэл тоо $k$ ($1 ≤ k ≤ 3*10^{6}$) байна.

Гуравдугаар мөрөнд нэг бүхэл тоо $n$ ($0 ≤ n ≤ 5000$) байх ба өөрчлөлтүүдийн тоо юм. Дараагийн $n$ мөрөнд өөрчлөлтүүдийг хийгдэх дарааллаар нь тодорхойлно. Өөрчлөлт бүр $l_{i}$ ба $r_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ 10^{9}$) хоёр тоогоор тодорхойлогдох ба энэ нь $[l_{i}, r_{i}]$ үргэлжилсэн дэд дараалал нь идэвхжиж өөрийгөө хуулбарлах ба өөр дээрээ тэнийсэн хэлбэрээ залгана гэсэн үг.

Оролтын өгөгдөл нь зөв байх буюу ямар ч өөрчлөлт DNA дарааллалд оршин байхгүй элементүүд дээр хийгдэхгүй ба үүссэн DNA дараалал нь ядаж $k$ элементтэй байна.

DNA элементүүд нь 1-с эхлэн дугаарлагдах ба $[l, r]$ тэмдэглэл нь DNA дарааллын $l$-р элементээс эхлэн $r$-р элемент дээр дуусах $r - l + 1$ элементтэй үргэлжилсэн дэд дарааллыг илэрхийлнэ.

Гаралт

Нэг мөрөнд өөрчлөгдсөн DNA дарааллын эхний $k$ үсгийг хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
GAGA
4
0
Гаралт
GAGA
Оролт
ACGTACGT
16
2
1 2
2 8
Гаралт
ACCAGTACCGACATCG

Тэмдэглэл

Хоёр дахь жишээн дээр эхний өөрчлөлтийн дараа дараалал "$ACCAGTACGT$" болно. Хоёр дахь өөрчлөлтийн дараа дараалал "$ACCAGTACCGACATCGT$" болно.

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