G3. Сайн дэд тэмдэгт мөрүүд

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

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

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

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

Ухаалаг Минж саяхнаас үгэн тоглоомд сонирхолтой болжээ. Уг тоглоом нь дараах байдлаар явагдана: $s$ тэмдэгт мөрийн ялгаатай сайн дэд тэмдэгт мөрүүдийн тоог тоолно. Тэмдэгт мөрийг сайн эсэхийн тодорхойлохдоо тоглоомын дүрмийг ашиглана. Нийтдээ $n$ ширхэг тоглоомын дүрэм байх ба дүрэм болгон нь $(p, l, r)$ гэсэн гурвалаар дүрслэгдэнэ. Энд $p$ нь тэмдэгт мөр байх ба $l$ болон $r$ $(l ≤ r)$ нь бүхэл тоонууд байна. Хэрэв $p$ тэмдэгт мөр дотор $t$ тэмдэгт мөрийн давтагдах тоо нь $l$-ээс $r$-ын хооронд байвал ($l$ эсвэл $r$ байж болно) бид $t$ тэмдэгт мөр нь $(p, l, r)$ дүрэмд захирагдаж байна гэж үзэх юм. Жишээлбэл, "$ab$" тэмдэгт мөр нь ("$ab$", $1$, $2$) болон ("$aab$", $0$, $1$) дүрмүүдэд захирагдах боловч ("$cd$", $1$, $2$) болон ("$abab$", $0$, $1$) дүрмүүдэд захирагдахгүй.

$s = s_{1}s_{2}... s_{|s|}$ ($|s|$ нь $s$-ын урт) тэмдэгт мөрийн дэд тэмдэгт мөр $s[l... r]$ $(1 ≤ l ≤ r ≤ |s|)$ нь тэмдэгт мөр $s_{l}s_{l + 1}... s_{r}$ байх юм.

$p$ тэмдэгт мөр дотор $t$ тэмдэгт мөрийн давтагдах тоо гэдэг нь $p[l... r] = t$ байх $l, r$ $(1 ≤ l ≤ r ≤ |p|)$ бүхэл тоон хосуудын тоо юм.

Хэрэв $t$ тэмдэгт мөр нь бүх $n$ дүрэмд захирагдаж байвал бид уг тэмдэгт мөрийг сайн гэж үзнэ. Ухаалаг Минж танаас $s$ тэмдэгт мөрийн ялгаатай сайн дэд тэмдэгт мөрүүдийн тоог тооцоолох программ бичиж өгөхийг хүсжээ. Хэрэв $s[x... y] ≠ s[z... w]$ байвал $s[x... y]$ болон $s[z... w]$ дэд тэмдэгт мөрүүдийг ялгаатай гэж үзнэ.

Оролт

Эхний мөрөнд тэмдэгт мөр $s$ өгөгдөнө. 2-дахь мөрөнд бүхэл тоо $n$ өгөгдөнө. Дараагийн $n$ мөрийн мөр болгонд 1 дүрэм өгөгдөнө. Эдгээр мөр болгонд зайгаар тусгаарлагдсан нэг тэмдэгт мөр болон 2 бүхэл тоо $p_{i}, l_{i}, r_{i}$ хэлбэртэй байна ($0 ≤ l_{i} ≤ r_{i} ≤ |p_{i}|$). Оролтод өгөгдөх бүх тэмдэгт мөрүүд нь хоосон биш бөгөөд зөвхөн Англи цагаан толгойн жижиг үсгүүдээс тогтсон байна.

30-н оноо авах оролтын хязгаар (дэд бодлого G1):

  • $0 ≤ n ≤ 10$.
  • $s$ тэмдэгт мөрийн урт болон $p$ тэмдэгт мөрийн хамгийн их урт нь $ ≤ 200$ байна.

70-н оноо авах оролтын хязгаар (дэд бодлого G1+G2):

  • $0 ≤ n ≤ 10$.
  • $s$ тэмдэгт мөрийн урт болон $p$ тэмдэгт мөрийн хамгийн их урт нь $ ≤ 2000$ байна.

100-н оноо авах оролтын хязгаар (дэд бодлого G1+G2+G3):

  • $0 ≤ n ≤ 10$.
  • $s$ тэмдэгт мөрийн урт болон $p$ тэмдэгт мөрийн хамгийн их урт нь $ ≤ 50000$ байна.

Гаралт

$s$ тэмдэгт мөрийн сайн дэд тэмдэгт мөрүүдийн тоо болох ганц бүхэл тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
aaab
2
aa 0 0
aab 1 1
Гаралт
3
Оролт
ltntlnen
3
n 0 0
ttlneenl 1 4
lelllt 1 1
Гаралт
2
Оролт
a
0
Гаралт
1

Тэмдэглэл

Эхний жишээнд 3-н сайн дэд тэмдэгт мөр байна: «$aab$», «$ab$» болон «$b$».

2-дахь жишээд зөвхөн «$e$» болон «$t$» нь сайн дэд тэмдэгт мөр байна.

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