50054. A Hash Table

I'm a slow walker, but I never walk backwards.

Hash Table Definition

A hash table is a data structure that stores values in buckets. Each value has a key and a hash table uses a hash function to compute the index of the bucket into which the desired value will be stored. Ideally, the hash function will assign each key to a unique bucket, but it is possible that two keys will generate the same index, so that they will be assigned to the same bucket. This is called collision. As a result, we will assume that a bucket can have more than one value.

Task Description

Your task is first to build a hash table, then use it to answer queries. Given $N$ strings, store them into a hash table, and given $Q$ queries then output its bucket index if existing in hash table, otherwise, output $-1$. You should use a hash function to compute hash table index and put the string into that bucket. Note that collision do occur and a bucket can have multiple values. When a collision occurs, the new value will be append to the end of the bucket. We define the hash function as the sum of the ASCII code of each alphabet of the string plus the sum of the numeric values of the digits in the string, moduled by $S$, the size of the hash table. For example, if we are given a string ABC123 and hash table size is $100$, then its hash table index is $\lbrack (65 + 66 + 67) + (1 + 2 + 3)]$ % $100 = 4$. That is, you should put the string ABC123 into the fourth bucket.

Now after we built the hash table we can answer the queries. The queries are also strings. If a string is in the hash table, then we can quickly find in the bucket using the hash table. If the string is not in the hash table, we can also quickly determine that by check the values stored in the bucket, indexed by the hash function.

Input Format

Input contains one test case. The first line contains three integers $S$, $N$ and $Q$, indicating the size of hash table, the number of strings to build the hash table, and the number of queries. For the following $N + Q$ lines, each line contains a string. Characters of each string are all alphabets or digits.

Technical limitation

  • $3 \leq S \leq 1000$
  • $1 \leq N \leq 10000$
  • $1 \leq Q \leq 20000$
  • $1 \leq string$ $length \leq 100$

Output Format

For each query string, output the bucket index if it exists in the hash table, otherwise output -1.

Sample Input

5 5 3
ABC123
AAA333
BBB222
ABC
ABCDEF
A
AAA333
B

Sample Output

-1
4
-1

Discussion