Hôm nay Khánh, nhà khoa học đại tài đã lập trình chương trình phân tích xâu. Chương trình của Khánh hoạt động như sau:

• Ban đầu, chương trình có \(n\) xâu không rỗng được đánh số từ \(1\) đến \(n\), mỗi xâu gồm các chữ cái latin viết hoa có tổng độ dài không quá \(2 \times 10^5\) và mỗi xâu có một giá trị nguyên dương \(v_i\).
• Tiếp đó, chương trình sẽ thực hiện lần lượt \(q\) truy vấn, mỗi truy vấn thuộc một trong \(2\) dạng:
  • \(1\) \(x\) \(k\): truy vấn này sẽ gán giá trị của xâu thứ \(x\) thành \(k\).
  • \(2\) \(s\): cho xâu \(s\) gồm các chữ cái latin viết hoa, xét tất cả các xâu trong \(n\) xâu đã cho, gọi \(f_i\) là số lần xuất hiện của \(s\) dưới dạng xâu con liên tiếp của xâu thứ \(i\). Ta cần tính tổng \(f_i \times v_i\).

Bây giờ Khánh đố các bạn là với mỗi truy vấn loại \(2\) thì tổng \(f_i \times v_i\) là bao nhiêu?

Input

• Dòng đầu tiên lần lượt là \(2\) số nguyên dương \(n\) và \(q\) (\(1 \le n, q \le 10^5\)).
• Dòng tiếp theo là giá trị các xâu \(v_1, v_2, ..., v_n\) (\(1\le v_i \le 10^6\) với \(1 \le i \le n\)).
• Dòng thứ \(i\) trong \(n\) dòng tiếp theo là xâu thứ \(i\) trong \(n\) xâu ban đầu, tổng độ dài của \(n\) xâu này không quá \(2 \times 10^5\).
• \(q\) dòng tiếp theo, mỗi dòng biểu thị một truy vấn có dạng \(1\) \(x\) \(k\) (\(1 \le x \le n, 1 \le k \le 10^6\)) hoặc \(2\) \(s\), tổng độ dài các xâu của toàn bộ truy vấn \(2\) không quá \(2 \times 10^5\).

Output

• Với mỗi truy vấn loại \(2\) in ra kết quả trên một dòng.

Scoring

• Subtask 1 (\(18\%\) số điểm): tổng độ dài các xâu trong \(n\) xâu ban đầu không quá \(10^3\), tổng độ dài các xâu trong toàn bộ truy vấn \(2\) không quá \(10^3\).
• Subtask 2 (\(19\%\) số điểm): \(n, q \le 10^3\).
• Subtask 3 (\(20\%\) số điểm): không có truy vấn loại \(1\).
• Subtask 4 (\(21\%\) số điểm): một xâu chỉ bị thay đổi giá trị tối đa \(1\) lần.
• Subtask 5 (\(22\%\) số điểm): không có ràng buộc gì thêm.

Example

3 4
1 1 1
ABABAA
AAAA
BABBBA
2 AB
2 AAA
1 1 3
2 AB 

3
2
7