C. Орлуулга

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

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

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

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

Даниелд Англи жижиг үсэгнүүд болон цэгнүүдээс (тэмдэгт ".") бүтсэн $s$ тэмдэгт мөр байна. $replacement$ функц нь дараах үйлдлүүдийг гүйцэтгэдэг: ".." дэд тэмдэгт мөрийг хайж олно, бүх олсон дэд тэмдэгт мөрнөөс хамгийн эхний дэд тэмдэгт мөрийг сонгон "." тэмдэгт мөрөөр солино. Өөрөөр хэлвэл хамгийн эхний дараалсан 2 цэгийг 1 цэгээр солино гэсэн үг. Хэрвээ тэмдэгт мөр $s$-д дараалсан 2 цэг байхгүй бол юу ч өөрчлөгдөхгүй.

$f(s)$ нь $s$ тэмдэгт мөрөнд дараалсан 2 цэг байхааргүйгээр хамгийн багадаа хэдэн удаа $replacement$ функцийг ашиглах вэ? гэдгийг тооцоолдог функц юм.

Танд $m$ ширхэг даалгавар байгаа бөгөөд даалгавар болгон нь $s$ тэмдэгт мөрний $x_{i}$ ($1 ≤ x_{i} ≤ n$) дэхь тэмдэгтийн оронд $c_{i}$ тэмдэгтийг орлуулна. Даалгавар болгоны дараах $f(s)$ функц болгоныг тооцоолно уу.

Даниелийг бүх даалгавраа биелүүлэхэд туслаарай.

Оролт

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

2 дахь мөрөнд $n$ ширхэг Англи жижиг үсэг болон цэгээс бүтсэн $s$ тэмдэгт мөр өгөгдөнө.

Дараагийн $m$ ширхэг мөрөнд даалгавруудын тайлбар өгөгдөнө. $i$ дэхь мөрөнд 2 ширхэг бүхэл тоо $x_{i}$, $c_{i}$ ($1 ≤ x_{i} ≤ n$, $c_{i}$ өгөгдөнө. Энд $s$ тэмдэгт мөрний $x_{i}$ дэхь тэмдэгтийн оронд $c_{i}$ тэмдэгтийг орлуулна.

Гаралт

$m$ ширхэг мөрний $i$ дэхь мөрөнд $i$ ширхэг даалгавар биелүүлсэний дараах $f(s)$ функцыг тооцоолон хэвлэнэ үү.

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

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

Оролт
10 3
.b..bz....
1 h
3 c
9 f
Гаралт
4
3
1
Оролт
4 4
.cc.
2 .
3 .
2 a
1 a
Гаралт
1
3
1
1

Тэмдэглэл

Эхний жишээнд (орлуулагдаж буй цэгүүдийг дөрвөлжин хаалтаар тусгаарласан):

Анхны тэмдэгт мөр бол "$.b..bz....$".

  • Эхний даалгаврын дараа: $f($hb..bz....$)$ = 4    ($hb[..]bz....$ $->$ $hb.bz[..]..$$ ->$ $hb.bz[..].$ $->$ $hb.bz[..]$  $->$ $hb.bz.$)
  • 2 дахь даалгаврын дараа: $f($hbс.bz....$)$ = 3    ($hbс.bz[..]..$ $ -> $ $hbс.bz[..].$ $ -> $ $hbс.bz[..]$ $ -> $ $hbс.bz.$)
  • 3 дахь даалгаврын дараа: $f($hbс.bz..f.$)$ = 1    ($hbс.bz[..]f.$ $ -> $ $hbс.bz.f.$)

2 дахь жишээнд:

Анхны тэмдэгт мөр бол "$.cc.$".

  • Эхний даалгаврын дараа: $f($..c.$)$ = 1    ($[..]c.$ $ -> $ $.c.$)
  • 2 дахь даалгаврын дараа: $f($....$)$ = 3    ($[..]..$ $ -> $ $[..].$ $ -> $ $[..]$ $ -> $ $.$)
  • 3 дахь даалгаврын дараа: $f($.a..$)$ = 1    ($.a[..]$ $ -> $ $.a.$)
  • 4 дэхь даалгаврын дараа: $f($aa..$)$ = 1    ($aa[..]$ $ -> $ $aa.$)
Сэтгэгдлүүдийг ачааллаж байна...