tell him the name of the superhero that should deal with that supervillain.
Q3: Superheroes
Supervillains are tired of Toronto condo rental prices, so they are leaving Toronto for Mississauga.
Luckily, we have n valiant superheroes that can deal with them. The i-th superhero (0 <= i < n) has a name name[i], an intelligence score in[i], and a strength score s[i].
There are m supervillains flocking to Mississauga. After thorough investigation, Detective Zingaro has determined that the supervillains can be classified into three categories for how to deal with them:
-
A type 1 supervillain has an intelligence score int. Detective Zingaro needs to assign a superhero whose intelligence is at least as much as int to this supervillain. Moreover, to be efficient with his resources, he must assign the superhero with the minimum intelligence who satisfies this requirement.
-
A type 2 supervillain has a strength score st. The detective needs to assign a superhero whose strength is at least as much as st to this supervillain. Similar to above, he must assign the superhero with the minimum strength that meets this requirement.
-
Finally, a type 3 supervillain has a mixed score g, meaning that the superhero x assigned to them needs to have in[x] + s[x] >= g. Again, the detective is interested in the superhero with the smallest in[x] + s[x] that satisfies this requirement.
Detective Zingaro has asked for your help. For each of the supervillains, tell him the name of the superhero that should deal with that supervillain.
Note: A superhero can be assigned to multiple supervillains (or none at all).
Note: whenever there are multiple superheroes that satisfy the given requirements for a supervillain, report the one whose name is lexicographically smallest (i.e. the one that’s the smallest according to Python’s ordering of strings). It’s guaranteed that superheroes have distinct names.
Hint: Tuples of multiple elements may be helpful here. In python, you can compare two tuples (a, b) and (c, d). If a and c are different, the result is the same as comparing a and c. If a and c are equal, the result is the same as comparing b and d. You can even sort these tuples!
Input
The first line of the input contains a single integer n denoting the number of superheroes.
The next three lines describe the superheroes. The first line contains n space-separated strings, specifying the names of the superheroes. The second line contains n space-separated integers, specifying the list in. Finally, the third line specifies the list s.
The next line contains a single integer m denoting the number of supervillains. m lines will follow describing them, one per line. Each of these lines starts with an integer t denoting the type of the villain (1, 2, or 3), followed by an integer specifying the corresponding threshold.
Output
Your output should consist of m strings separated by spaces. The i-th one should be the name of the superhero assigned to the i-th supervillain. If no superhero meets the requirements for a supervillain, output none for that supervillain instead.
Constraints
- 1 <= n, m <= 150000
- Intelligence scores, strength scores, and thresholds are all in range [1, 500000].
- Superhero names are between 1 and 6 characters long and contain only lowercase English letters.
- No two superheroes have the same name.
- No superhero’s name is “none”
Time Limit
Your program must finish running on any valid input within 5 seconds.
Sample Input 1
5
batman catman pacman peach mario
1 3 7 10 8
4 7 7 3 1
4
1 4
2 7
3 11
1 11
Sample Output 1
pacman catman peach none
Sample 1 Explanation
- The first line indicates that there are 5 superheroes.
- Lines 2-4 describe the superheroes. For instance, the second one is named “catman” and has an intelligence score of 3 and a strength score of 7.
- Line 5 indicates that there are 4 supervillains to deal with. These supervillains are described in the following 4 lines.
- For the second supervillain, both catman and pacman satisfy the requirements of Detective Zingaro. However, catman is lexicographically smaller than pacman, so you should report catman as the answer.
Sample Input 2
5
a b c d e
1 2 3 5 8
8 5 3 2 1
6
1 5
3 7
2 1
2 8
3 6
1 4
Sample Output 2
d b e a c d
Step by step
Solved in 2 steps with 1 images
