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.

Input

• 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\).

Output

• Gồm nhiều dòng, mỗi dòng là câu trả lời cho truy vấn loại \(2^{nd}\).

Example

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

1
2