TWICE6

Tác giả:

Dạng bài

Điểm: 400 Thời gian: 3.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

SPyofgame đang chơi một trò chơi với người chủ của mình. Người chủ cho SPyofgame N xâu ký tự khác nhau và Q truy vấn:

\(1^{st}\) x: Người chủ sẽ cho SPyofgame một xâu x.
\(2^{nd}\) k: Người chủ cho một số nguyên K là số thứ tự của xâu thứ K trong N xâu ban đầu. SPyofgame sẽ phải trả lời câu hỏi rằng xâu thứ K đó là xâu con của tất cả bao nhiêu xâu x mà người chủ đã cho.

Bạn hãy giúp SPyofgame giải quyết các câu hỏi trên.

Dòng đầu tiên là số nguyên dương N là số xâu ban đầu. (1\(\leq\) * N\(\leq\) * *\(10^6\)*).
N dòng tiếp theo, mỗi dòng gồm một xâu là các chữ cái trong bảng chữ cái tiếng Pháp. Tổng độ dài tất cả các xâu sẽ không vượt quá \(2.10^6\) (Link sẽ được để trong phần mô tả của video, à lộn, phần comment).
Dòng tiếp theo là số nguyên dương Q là số lượng truy vấn mà nguời chủ đặt ra.
Q dòng cuối cùng bao gồm các truy vấn loại \(1^{st}\) và \(2^{nd}\). Biết rằng nếu là truy vấn loại \(1^{st}\), tổng độ dài tất cả các xâu x sẽ không vượt quá \(2.10^6\).

Test 1

Input

2
ab
b
5
1 baab
2 2
1 cdab
1 bbbbaaa
2 1

Output

1
2

Note

Ở truy vấn đầu tiên, người chủ cho SPyofgame xâu đầu tiên là baab.
Ở truy vấn thứ hai, người chủ cho SPyofgame số nguyên K = 2, tức là xâu b. Ta thấy xâu b là xâu con duy nhất của xâu baab (Vì người chủ mới cho 1 xâu duy nhất) nên câu trả lời là 1.
Ở truy vấn thứ ba, người chủ cho SPyofgame thêm một xâu nữa là là cdab.
Ở truy vấn thứ tư, người chủ cho SPyofgame thêm một xâu nữa là là bbbbaaa.
Ở truy vấn thứ năm, người chủ cho SPyofgame số nguyên K = 1, tức là xâu ab. Ta thấy rằng xâu ab là xâu con của hai xâu baab và cdab nhưng không phải xâu con của bbbbaaa nên câu trả lời là 2.

Bình luận