407643: GYM102862 G Strange Queries

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Strange Queriestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given $$$n$$$ strings, and you need to answer $$$q$$$ queries. Each query is composed of two strings $$$l_i$$$ and $$$r_i$$$. For such a query, you need to count the number of the given strings such that either it has $$$l_i$$$ as a prefix, $$$r_i$$$ as a suffix, or both (thus, a string that has $$$l_i$$$ for a prefix and $$$r_i$$$ for a suffix should be counted once).

Input

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$), the number of strings. Then follow $$$n$$$ strings, each in its own line. The next line contains a single integer $$$q$$$ ($$$1 \leq q \leq 10^5$$$), the number of queries. Then $$$q$$$ lines follow, the $$$i$$$-th of them contains two strings $$$l_i$$$ and $$$r_i$$$. None of the strings in the input is empty.

The sum of the lengths of all strings in the input does not exceed $$$10^5$$$ (including queries). All strings consist of lowercase English alphabet letters only.

Output

For each query, output the number of the given strings that have either the given prefix or the given suffix (or both).

ExampleInput
3
bat
eca
baca
1
ba ca
Output
3

加入题单

上一题 下一题 算法标签: