Hùng đang phát triển một phần mềm diệt virus dựa trên nguyên tắc so khớp mẫu. Theo đó, cậu có tập S các xâu nhị phân là mẫu thường gặp trong mã nguồn của virus (mã độc). Mỗi tệp tin \(f\) có thể được hiểu như một xâu nhị phân, độ tương thích của \(f\) với mẫu \(x\) là số lần xuất hiện của \(x\) ở trong \(f\) (xuất hiện theo nghĩa bằng với một đoạn con liên tiếp).

Để đánh giá \(f\) có bị nhiễm virus hay không, Hùng muốn tính tổng độ tương thích của \(f\) với mọi xâu trong S. Trong quá trình sử dụng, Hùng có thể cập nhật thêm các mẫu virus mới. Ban đầu Hùng chưa có mẫu virus nào được báo cáo. Cụ thể bạn cần thực hiện hai loại truy vấn sau:

• Loại 1: \(0 x\): Thêm xâu \(x\) vào tập \(S\). Nếu \(x\) đã xuất hiện trong \(S\), Hùng vẫn thêm \(x\) vào (theo cậu, càng có nhiều người dùng báo cáo một mẫu thì mẫu đó càng quan trọng). Có thể hiểu \(S\) là một multiset.

• Loại 2: \(1 f\): Tính toán và đưa ra tổng số lần xuất hiện của các xâu trong \(S\) trên xâu \(f\)

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương \(Q\)

• \(Q\) dòng tiếp theo mỗi dòng mô tả một truy vấn: \(0 x\) hoặc \(1 f \)

Kết quả

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

Hạn chế : \(1 ≤ Q ≤ 10^6\) , tổng độ dài tất cả các xâu đầu vào không quá \(2 × 10^6.\)

• Subtask 1: \(|S|≤ 10.\)

• Subtask 2: Các truy vấn loại hai nằm liên tiếp nhau.

• Subtask 3: Ràng buộc gốc.

Sample Input

5 
0 0 
0 1 
0 01 
1 10011001 
1 01010011

Sample Output

10
11