Tại Thư viện Cổ đại, trongphithien và p2o2HuaGiaBao phát hiện ra rằng mỗi ký tự trong "Xâu Khởi Nguyên" sở hữu một trọng số năng lượng ẩn sau mỗi lần xuất hiện. Khi "Zero-Point Corruption" xâm chiếm, các ký tự thay đổi vị trí kéo theo sự hỗn loạn năng lượng.
Cho xâu \(S\) độ dài \(n\) gồm các chữ cái thường và một hằng số khoảng cách \(K\). Mỗi vị trí \(i\) trên xâu có một mức năng lượng cố định ban đầu là \(V_i\). Thực hiện \(Q\) truy vấn thuộc hai loại:

• Loại \(1\) (1 i c): Thay đổi ký tự tại vị trí \(i\) thành ký tự \(c\). Mức năng lượng \(V_i\) tại vị trí đó được giữ nguyên không đổi.
• Loại \(2\) (2 L R c): Chọn một tập hợp các vị trí \(i_1, i_2, \dots, i_m\) nằm trong đoạn \([L, R]\) sao cho:
• Tất cả các vị trí được chọn đều đang chứa ký tự \(c\) (\(S_{i_j} = c\)).
• Khoảng cách giữa hai vị trí liên tiếp được chọn phải cách nhau ít nhất một khoảng cách \(K\) (tức là \(i_j - i_{j-1} \ge K\) với mọi \(j \ge 2\)).
• Tổng giá trị năng lượng \(V_{i_1} + V_{i_2} + \dots + V_{i_m}\) đạt giá trị lớn nhất.

Input

• Dòng đầu tiên gồm ba số nguyên \(n, Q, K\) (\(1 \le n, Q \le 5\times 10^4; 1 \le K \le n\)).
• Dòng thứ hai gồm một xâu \(S\) độ dài \(n\) gồm các ký tự chữ cái latin thường từ a đến z.
• Dòng thứ ba gồm \(n\) số nguyên \(V_1, V_2, \dots, V_n\) (\(1 \le V_i \le 10^9\)) — mảng năng lượng cố định tại mỗi vị trí.
• \(Q\) dòng tiếp theo: Mỗi dòng mô tả một truy vấn:
  • Truy vấn loại \(1\): 1 i c (với \(1 \le i \le n\) và \(c\) là ký tự thường).
  • Truy vấn loại \(2\): 2 L R c (với \(1 \le L \le R \le n\) và \(c\) là ký tự thường).

Output

• Với mỗi truy vấn loại \(2\), in ra một số nguyên duy nhất trên một dòng là tổng giá trị năng lượng tối ưu lớn nhất tìm được. Nếu không có ký tự \(c\) nào trong đoạn, in ra 0.

Example

7 3 3
abcabca
1 10 5 2 8 3 6
2 1 7 a
1 4 b
2 1 7 a

9
7

6 2 2
aaaaaa
10 20 5 30 2 15
2 1 6 a
1 4 c

65