{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":" \n \u003cp\u003eVivy finds that some domains can be visited faster using different VPNs (Virtual Private Network). So she decides to set up a system to automatically transfer requests to different VPNs.\u003c/p\u003e \n \u003cp\u003eFirst of all, she has to set up configurations.\u003c/p\u003e \n \u003cp\u003eThere are multiple rules in the configurations. The format of a rule is: [domain pattern] [VPN name]. If a domain matches the [domain pattern] of a rule, we say that the domain matches the rule, and all visits to this domain should be transferred to [VPN name].\u003c/p\u003e \n \u003cp\u003eTo make the configurations short, Vivy decided to use two kinds of wildcards which are \"*\" and \"#\". \u0026nbsp;Both \"*\" and \"#\" matches any strings consisting of lowercase alphabets, digits, dots and hyphens (\u0027-\u0027). But a domain matches the rules with \"#\" wildcard only if it doesn\u0027t match any other rules.\u003c/p\u003e \n \u003cp\u003eA domain pattern is legal, if and only if it satisfies all the following conditions:\u003c/p\u003e \n \u003cp\u003e1. The domain pattern consists of wildcards, lowercase alphabets, digits, dots and hyphens.\u003c/p\u003e \n \u003cp\u003e2. The domain pattern does not start with a dot, and does not end with a dot.\u003c/p\u003e \n \u003cp\u003e3. Any two dots in the domain pattern are not adjacent.\u003c/p\u003e \n \u003cp\u003e4. If there is a wildcard, the wildcard must be at the beginning of the domain pattern. And the wildcard must precede a \".\", or no character follows it.\u003c/p\u003e \n \u003cp\u003e5. A hyphen in the domain pattern must be between two lowercase alphabets.\u003c/p\u003e \n \u003cp\u003eA VPN name is legal, if and only if it satisfies all the following conditions:\u003c/p\u003e \n \u003cp\u003e1. The VPN name consists of lowercase alphabets, digits and hyphens.\u003c/p\u003e \n \u003cp\u003e2. The VPN name starts with lowercase alphabets.\u003c/p\u003e \n \u003cp\u003e3. A hyphen in the VPN name must be between two lowercase alphabets.\u003c/p\u003e \n \u003cp\u003eTwo rules are considered conflict, if it satisfies any one of the following conditions:\u003c/p\u003e \n \u003cp\u003e1. There exist a domain without wildcards which can match both of them at the same time. For example, if the domain pattern of rule A is \"*.cn\" and the domain pattern of rule B is \"a.cn\", then rule A and rule B are conflict because domain “a.cn” can match both of them.\u003c/p\u003e \n \u003cp\u003e2. One of them can never be matched because of the other one. For example, \"#.pku.cn\" can never be matched if the other one is \"*.cn\".\u003c/p\u003e \n \u003cp\u003eA rule is considered invalid, if it satisfies any one of the following conditions:\u003c/p\u003e \n \u003cp\u003e1. The has an illegal domain pattern.\u003c/p\u003e \n \u003cp\u003e2. The rule has an illegal VPN name.\u003c/p\u003e \n \u003cp\u003e3. The rule is conflict with a valid rule that appears before it.\u003c/p\u003e \n \u003cp\u003eNow she wants to write a program to parse the configurations and determine how many rules are invalid.\u003c/p\u003e \n \u003cp\u003eAnd she wants to know more things. A valid domain pattern without wildcard \"#\" can represent a set of domains. She wants to know, given a set of domains, how many valid rules matches the set, ie. how many rules satisfy that there exists a domain without wildcards in the set which matches the rule.\u003c/p\u003e \n "}},{"title":"Input","value":{"format":"HTML","content":" \n \u003cp\u003eThe input consists of multiple test cases, up to 10.\u003c/p\u003e \n \u003cp\u003eFor each test case:\u003c/p\u003e \n \u003cp\u003eThe first line contains an integer N, indicating the number of rules. (1 \u0026lt;\u003d N \u0026lt;\u003d 50000)\u003c/p\u003e \n \u003cp\u003eThen N lines followed, each line contains two strings separated by a space, indicating domain pattern and VPN name of a rule.\u003c/p\u003e \n \u003cp\u003eThe total length of the strings in rules will not exceed 1100000.\u003c/p\u003e \n \u003cp\u003eThe next line contains an integer M, indicating the number of queries. (1 \u0026lt;\u003d M \u0026lt;\u003d 50000)\u003c/p\u003e \n \u003cp\u003eThen M lines followed. Each line contains a domain pattern representing a set of domains. For each query, you should answer how many valid rules matches the given set. It is guaranteed that the given domain pattern is legal, and does not contain wildcard \"#\".\u003c/p\u003e \n \u003cp\u003eThe total length of the strings in queries will not exceed 1100000.\u003c/p\u003e \n "}},{"title":"Output","value":{"format":"HTML","content":" \n \u003cp\u003eFor each test case:\u003c/p\u003e \n \u003cp\u003eThe first line contains an integer, indicating the number of invalid rules.\u003c/p\u003e \n \u003cp\u003eThen M lines followed, each line is an integer, indicating the number of matched valid rules for the corresponding query.\u003c/p\u003e \n "}},{"title":"Sample Input","value":{"format":"HTML","content":" \n \u003cpre\u003e11\r\na.c a.c\r\npoj.org vpn-china\r\nwww.pku.edu.cn vpn-pku1\r\nmail.pku.edu.cn vpn-pku1\r\n*.test.pku.edu.cn vpn-pku2\r\n*.test.pku.edu.cn vpn-pku2\r\n*.a.test.pku.edu.cn vpn-pku2\r\n*.test2.pku.edu.cn vpn-pku2\r\n*.pku.edu.cn vpn-pku2\r\n#.pku.edu.cn vpn-pku0\r\n#.www.pku.edu.cn vpn-pku0\r\n5\r\na.c\r\nmail.pku.edu.cn\r\n*.test.pku.edu.cn\r\n*.pku.edu.cn\u003c/pre\u003e \n "}},{"title":"Sample Output","value":{"format":"HTML","content":" \n \u003cpre\u003e5\r\n0\r\n1\r\n1\r\n5\r\n6\u003c/pre\u003e \n "}}]}