Танд $n$ урттай Англи цагаан толгойн эхний $k$ жижиг үсгээс бүрдэх $s$ тэмдэгт мөр өгөгдсөн.

Бид $q$ тэмдэгт мөрийн $c$ давталтаас бүрдэх тэмдэгт мөр буюу $q$ тэмдэгт мөрийн $c$ давталтыг тэмдэгт мөр хэлбэрээр тодорхойлно. Жишээлбэл "$acbacbacbacb$" тэмдэгт мөр бол $"abc"$ тэмдэгт мөрийг $4$ удаа давтсан тэмдэгт мөр.

Хэрвээ $b$ тэмдэгт мөр $a$ тэмдэгт мөрийн зарим үсгийг арилгаад гарч байвал $a$ тэмдэгт мөрийг $b$ тэмдэгт мөрийг дэд дараалал хэлбэрээр өөртөө агуулж байна гэж хэлье.

$p$-г Англи цагаан толгойн эхний $k$ жижиг үсгүүдийг сэлгэж үүссэн тэмдэгт мөр гэе. Бид $p$ тэмдэгт мөрийн $d(p)$ ширхэг давталт $s$ тэмдэгт мөрийг дэд дараалал хэлбэрээр өөртөө агуулж чадах хамгийн бага бүхэл тоог олдог $d(p)$ функцийг тодорхойлно.

$s$ тэмдэгт мөрөнд хийж болох дараах хоёр төрлийн $m$ үйлдэл байгаа:

1. $l_{i}$-с $r_{i}$ хүртэлх байрлалд байгаа бүх тэмдэгтүүдийг $c_{i}$ тэмдэгтээр солих.
2. Англи цагаан толгойн эхний $k$ жижиг үсгүүдийг сэлгэж үүссэн өгөгдсөн $p$-н хувьд $d(p)$ функцийн утгыг ол.

Бүх үйлдлүүд оролтонд харагдаж буй дарааллаараа ээлжлэн хийгдэнэ. Таны ажил бол хоёр дахь төрлийн үйлдэл бүрийн хувьд $d(p)$ функцийн утгыг тодорхойлох юм.

Оролт

Эхний мөрөнд гурван эерэг бүхэл тоон утга $n$, $m$ ба $k$ ($1 ≤ n ≤ 200 000, 1 ≤ m ≤ 20000, 1 ≤ k ≤ 10$) байх ба харгалзан $s$ тэмдэгт мөрийн урт, үйлдлийн тоо, цагаан толгойн үсгийн хэмжээ. Хоёр дахь мөрөнд $s$ тэмдэгт мөр өөрөө байна.

Дараагийн $m$ мөр бүрт нэг үйлдлийн тодорхойлолт байна:

1. Эхний төрлийн үйлдэл нь $1$-ээр эхлэх ба залгуулаад $l_{i}$, $r_{i}$, $c_{i}$ байх ба $l_{i}$-с $r_{i}$ байрлалд байгаа бүх тэмдэгтийг $c_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ n$) тэмдэгтээр солихыг заах ба $c_{i}$ нь Англи цагаан толгойн эхний $k$ жижиг үсгийн нэг байна.
2. Хоёр дахь төрлийн үйлдэл нь $2$-оор эхлэх ба залгуулаад Англи цагаан толгойн эхний $k$ жижиг үсгийг сэлгэж үүссэн тэмдэгт мөр байна.

Гаралт

Хоёр дахь төрлийн үйлдэл бүрийн хувьд $d(p)$ функцийн утга.

Эхний үйлдлийн дараа тэмдэгт мөр $s$ нь $abbbbba$ болно.

Хоёр дахь үйлдлийн хариу нь $abc$-н $6$ давталт: $ABcaBcaBcaBcaBcAbc$.

Гурав дахь үйлдлийн дараа тэмдэгт мөр $s$ нь $abbcbba$ болно.

Дөрөвдүгээр үйлдлийн хариу нь $cba$-н $5$ давталт: $cbAcBacBaCBacBA$.

Том үсэгнүүд нь $s$-н тэмдэгтүүдийн тохиолдож буй тохиолдлууд юм.