Mobile Selection

★★★★★

1 votes

Algorithms, Binary Search, Medium, Searching, Sorting, hiring

Details

Submissions

Discussion

Editorial

Problem

John has opened a new mobile shop. Each mobile is having following properties associated to it :

Operating System ( Windows, Android or iOS)
RAM Size (2, 4 or 8 GB)
Memory Space (32 or 64 GB)
Price
Rating (based on other features like camera, touch quality, etc)

Now a customer comes to the store and tells his choice of Operating System, RAM size, Memory Space and his budget that he is willing to spend on the mobile. John will give the customer that mobile phone whose rating is maximum which also satisfies the criteria of Operating System, RAM size and Memory Space as specified by that customer and also whose price lies within the customer’s budget. If more than one eligible phone have maximum rating then, he can give any phone to the customer.

Note : All the queries are independent of each other.

Hint: Maintain a list of phone prices and rating for each combination of OS,RAM and Memory. For a given combination, find the one with best rating in given budget.

Input Format

First line contains an integer N denoting number of mobile phones in John's shop.
Each of the next N lines contains a string S followed by four integers A, B, C and D respectively where S denotes the operating system of the phone, A denotes the ram size of the phone, B denotes the memory space of the phone, C denotes the price of the phone and D denotes the rating of the phone.
Next line contains an integer Q denoting the number of customers who have visited John's shop.
Each of the next Q lines contains a string H followed by three integers E, F and G respectively where H denotes the choice of operating system of the phone required by the customer, E denotes the choice of ram size of the phone required by the customer, F denotes the choice of memory space of the phone required by the customer and G denotes the budget of the customer.

Output Format

For each query print the rating of the mobile phone given to customer by John as specified by the rules mentioned above.
If there is no mobile phone available in John's shop following the customer's constraints, print 1.
Answer for each query should be in new line.

Input Constraints

$1 \le N, Q \le 10^6$

$S, H$ ∈ { "windows", "android", "ios"}

$A, E$ ∈ {2, 4, 8}

$B, F$ ∈ {32, 64}

$1 \le C, D, G \le 10^9$

Sample Input

5
windows 2 32 100 100
windows 4 64 10 52
android 2 32 56 9
ios 2 32 20 63
windows 2 32 452 50
2
windows 2 32 500
ios 4 32 100

Sample Output

100
-1

Time Limit: 2

Memory Limit: 512

Source Limit:

Explanation

For query 1, there are two phones which satisfies the given criteria having ratings 100 and 50. 100 being the max of these two values is the final answer of this query.

For query 2, none of the mobile satisfies the given criteria, hence answer is -1.

Contributers:

Shiv Dhingra

Subham Gupta