LogDB

Time limit1sMemory limit1024 MB

Summary

Parse a database of facts with parenthesized argument lists, then answer queries whose arguments may contain variables, counting matching fact occurrences.

Level: Medium6 of 10
Topics: String, Hash map, Implementation, Simulation
Solved: No attempts yet

Problem

A LogDB database is filled with facts. A fact is a name with a body consisting of a parenthesized list of names. This is similar to a function call:

[ fact1(arg1, arg2 ,arg_3,4,4) thing(p1,arg2,p3). ]

$fact1$ is the name of the fact and the list of names in the body are the arguments of the fact. $thing$ is another fact.

The names in the list are separated by commas and optional whitespace. There is at least one name in the list.

Names consist of alphanumeric characters (a-z, A-Z, 0-9) plus ' $\_$ '. However, the name of a fact and the names in the body cannot start with an ' $\_$ '.

Names, parentheses, and commas may be preceded and followed by whitespace. However a fact or query cannot be split across lines.

Facts with different numbers of arguments are different facts.

A fact may appear multiple times in the database.

Queries are like facts except the argument list can contain variables. Variables are names that start with ' $\_$ '.

A query searches the database for facts with the same name as the query that have the same number of arguments as the query and where the names in the fact body match the names in the query body in their respective positions.

A variable consisting of only ' $\_$ ' is special and matches any name.

A variable other than ' $\_$ ' also matches any name, but if that variable appears more than once in a query, the names in the fact must be the same.

A query:

[ fact1(arg1,_,_,_check,_check) ]

matches $fact1(arg1, arg2 ,arg\_3,4,4)$ .

Variables are only defined in the query they appear in. They are not necessarily related if they are in different queries.

Input

The input consists of two sections: facts and queries. Judged data has no syntax errors.

The fact section consists of a series of lines of at most $200$ characters. That section is terminated by a blank line. Each line consists of facts which may (or may not) be separated by whitespace. The fact section consists of no more than $200$ lines.

The query section consists of a series of lines of at most $200$ characters. That section is terminated by end-of-file. Each line is a query. The query section consists of no more than $200$ lines.

Output

For each query print the number of facts returned by the query as an integer with no leading or trailing whitespace and no unnecessary leading zeros. If a matching fact appears multiple times in the database, count each occurrence.

Examples1

Example 1

Input

test(arg1, arg2,arg3) test(1,2,3,not4)5(five) five_seven(john_smith,10_17_57)
foo(1,2,3,4) foo(5,6,7,8) foo(1,2,7,8)arc(80) foo(abc,xyz)
bar(1,2) bar (7,8) zoom(8,7)
arc(80) nofoo(alpha,d1,d2,d1,d4,d1)
foo(bar,spam) foo(more,less)

test(_,_,_,_)
arc(80)
  foo(bar,_)
  foo(_,spam)
  foo(_,less)
  nofoo(_,_p1,_,_p1,_,_p1)
  foo(bar,less)
foo(_,_,_,_)
foo(_,_,_30,_40) 
foo(_,_,_30,_40)
foo(_,_,_30,_40)
foo(_x,_,_30,_40)
foo(_,_,_30,_40)

Expected output