552. Database optimization
Time limit per test: 3 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard
Alex worked at a big IT-company called Macrohard. Once, when he faced a large amount of data, he decided to leave this company and develop his own database which would be much better than all existing ones. When he was done with this he realized that the performance of some database queries might be improved. Alex uses AQL (Alex Query Language) which accidentally turned out to be exactly the same as the popular SQL. One of the most important problems he faced was the following.
Consider
n objects. The
i-th object has
ki (1 ≤
ki ≤ 4) properties in the form of
key=value
. Any object can't have two or more properties with the same key. Alex needs to improve the performance of the following query:
SELECT COUNT(*) FROM Objects WHERE key1=value1 AND... AND keyl=valuel
(1 ≤ l ≤ 4, all keys are distinct) This means that Alex's database has to find the number of objects which have properties
key1,
key2,...,
keyl with the values
value1,
value2,...,
valuel respectively. Even if an object has extra properties it should be counted.
Your task is to help Alex to write an efficient program to process such queries.
Input
The first line of the input contains a single integer
n (1 ≤
n ≤ 5 · 10
4) — the number of objects. Following
n lines describe objects by their properties. Each line contains the integer
ki (1 ≤
ki ≤ 4) followed by
ki tokens in the form of
keyi,j=
valuei,j separated by a single space. Both
keyi,j and
valuei,j consist of digits and lowercase Latin letters. The
keyi,j are distinct for each object. It is possible that different objects have exactly the same set of properties.
The next line of the input contains a single integer
m (1 ≤
m ≤ 10
5) — the number of queries. The following
m lines describe the queries. Each line contains a single integer
li (the number of properties that describe the
i-th query) followed by
li (1 ≤
li ≤ 4) tokens
keyi,j=
valuei,j separated by a single space, where
keyi,j and
valuei,j consist of digits and lowercase Latin letters. The
keyi,j are distinct for each query.
Lengths of
keyi,j and
valuei,j both for objects and queries are between 1 and 5 characters inclusive.
Output
Print
m lines, the
i-th line should contain the result of the
i-th query.
Example(s)
sample input | sample output |
4
3 width=5 ht=3 len=10
2 name=circ rad=5
2 name=circ rad=5
3 name=sqr width=5 ht=3
4
2 ht=3 width=5
1 name=circ
1 name=sqr
2 width=5 ht=03
| 2
2
1
0
|