Hoán vị bảng chữ cái (Alphabet Permutations)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Chuỗi $s$ dùng $k$ chữ đầu bảng chữ cái. Có thao tác gán một ký tự cho đoạn và truy vấn một hoán vị $p$. Gọi $d(p)$ là số bản sao nhỏ nhất của $p$ sao cho $p$ lặp $d(p)$ lần chứa $s$ như một subsequence; hãy in $d(p)$.

Input

Dòng đầu chứa $n,m,k$. Dòng thứ hai là chuỗi $s$ độ dài $n$, chỉ dùng $k$ chữ đầu của bảng chữ cái. Mỗi trong $m$ dòng sau là một thao tác:

• 1 l r c: gán mọi ký tự trong $[l,r]$ thành $c$.
• 2 p: $p$ là một hoán vị của $k$ chữ đầu; cần tính $d(p)$.

Output

Với mỗi thao tác loại 2, in giá trị $d(p)$ trên một dòng.

Subtask

• Subtask 1 (20%): $n$ và số thao tác không vượt 30; các điều kiện còn lại giữ như đề đầy đủ.

• Subtask 2 (30%): $n$ và số thao tác không vượt 3000; các điều kiện còn lại giữ như đề đầy đủ.

• Subtask 3 (50%): toàn bộ giới hạn:

• $1\le n\le2\cdot10^5$

• $1\le m\le20000$

• $1\le k\le10$

Ví dụ

Input

7 4 3
abacaba
1 3 5 b
2 abc
1 4 4 c
2 cba

Output

6
5

Giải thích

Sau thao tác gán đầu tiên, chuỗi là abbbbba; với hoán vị abc cần 6 bản sao. Sau lần gán tiếp theo, chuỗi thành abbcbba; với cba cần 5 bản sao.