Machine Learning

Popcorn Picks: Buckets Beat Distance

A cinema wants to recommend a genre by age group. Straight-line distances between ages don’t make sense; groups do. So ages are placed into buckets defined by given thresholds, and each bucket votes for its favorite genre.

You are asked to read a list of strictly increasing thresholds, then a preexisting set of viewer ages with their chosen genres. Every age belongs to exactly one bucket using these ranges:
(-∞, t1), [t1, t2), …, [tk, +∞).

For each new age, predict the majority genre among preexisting rows in the same bucket. If that bucket has no rows, fall back to the global majority genre from all preexisting rows. Break any ties by choosing the lexicographically smallest label. Labels contain no spaces.

The first line of the input contains a single integer k representing how many thresholds there are. The second line contains k strictly increasing integers t1 ... tk.

The next line contains a single integer n representing how many preexisting rows follow. Each of the next n lines contains an integer age and a label.

The next line contains a single integer q representing how many query ages follow. Each of the next q lines contains one integer age.

The program should print q lines. Each line should contain a single label - the predicted genre for the corresponding query age.

Input

Output

2
12 18
7
6 animation
12 animation
13 action
17 action
30 drama
45 drama
18 action
4
10
15
25
80

animation
action
drama
drama

3
13 17 60
8
11 animation
12 animation
14 comedy
15 comedy
20 drama
25 drama
40 action
50 action
4
16
35
9
75

comedy
action
animation
action

2
13 17
6
13 comedy
16 drama
17 action
17 comedy
12 animation
8 animation
3
13
17
5

comedy
action
animation

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue