Một thư viện điện tử đang lưu trữ \(N\) tài liệu, các tài liệu được đánh số từ \(1\) đến \(N\). Tài liệu thứ \(i\) có tên là một xâu ký tự \(S_i\).

Trong hệ thống có một tập các ký tự đang bị cấm. Ban đầu, tập ký tự bị cấm là rỗng. Một tài liệu được gọi là hợp lệ nếu tên của tài liệu đó không chứa bất kỳ ký tự nào đang bị cấm.

Hệ thống cần xử lý \(Q\) thao tác, mỗi thao tác thuộc một trong hai loại sau:

• 1 c: Nếu ký tự c chưa bị cấm thì thêm c vào tập ký tự bị cấm. Nếu ký tự c đang bị cấm thì bỏ c ra khỏi tập ký tự bị cấm.
• 2 L R: Hỏi trong các tài liệu từ vị trí \(L\) đến vị trí \(R\), có bao nhiêu tài liệu đang hợp lệ.

Sau mỗi thao tác loại \(2\), hãy in ra kết quả tương ứng.

Input

• Dòng đầu tiên chứa ba số nguyên dương \(N, Q, K\) (\(1 \le N, Q \le 2 \cdot 10^5, 1 \le K \le 16\)).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa xâu ký tự \(S_i\).
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một thao tác theo một trong hai dạng:
  • 1 c
  • 2 L R

Ràng buộc:

• Các xâu \(S_i\) chỉ gồm các chữ cái in thường đầu tiên trong bảng chữ cái, từ a đến ký tự thứ \(K\).
• Ký tự c trong thao tác loại \(1\) cũng thuộc các chữ cái từ a đến ký tự thứ \(K\).
• Tổng độ dài của tất cả các xâu \(S_i\) không vượt quá \(10^6\).
• \(1 \le L \le R \le N\).

Output

• Với mỗi thao tác loại \(2\), in ra một dòng là số lượng tài liệu hợp lệ trong đoạn được hỏi.

Example

5 7 4
ab
c
ad
bcd
d 
2 1 5
1 a
2 1 5
1 d
2 1 5
1 a
2 2 4

5
3
1
1