You want to buy a laptop. Each laptop has two parameters: **Rating & Price**. Your task is to buy a laptop with the highest rating within a given price range. Given * Q* tasks, each query consisting of price range required, you have to print the highest rated laptop that can be bought within that price range.

**Input format:**

- The first line contains
denoting the number of inputs.**N** - The following
lines contain**N**&**P**denoting price and range of a laptop.**R** - Next line contains
denoting the number of queries.**Q** - The following
lines contain two integers**Q**&**X**denoting the price range (inclusive).**Y**

**Output format:**

For each task Q, print the highest rating that can be bought within the range.

If you cannot get any laptop within the range, print *-1*.

**Constraints:**

**Sample Input:**

5

1000 300

1100 400

1300 200

1700 500

2000 600

3

1000 1400

1700 1900

0 2000

**Sample Output:**

400

500

600

**My approach:**

- Create a
**rating**array and initialize all its elements with**-1**. - For every price, fill the array with the maximum rating possible till that price.
- Continue till the maximum price/last element of rating array.
- Return
**rating[Y]**, because**Y > X**always.

**My problem:**

The above approach requires huge memory (atleast in C++) as the **rating** array will contain *10^9* elements (*because price range is from 1 to 10^9*). This is not possible because of memory constraints. We can probably use maps/dictionaries here, but then, they are heavy too. **This is where I need some guidance**.

**My solution (C++) (SIGSEGV):** *But works fine with sample test cases. PS: I know this is the right solution, but array size is the problem here.*

```
// This was already given
#define MAXSIZE 1000001
int solve()
{
//write code here
int rating[MAXSIZE];
fill(rating, rating+MAXSIZE, -1);
for (int i=0; i<N; i++)
rating[P[i]] = R[i];
int maxele = rating[0];
for (int i=0; i<MAXSIZE; i++)
{
rating[i] = max(maxele, rating[i]);
maxele = max(maxele, rating[i]);
}
return rating[Y];
}
```

**My solution (Py3) (Using dict):** *Partially accepted (1/5 test cases - 20/100)*

```
def Solve(N,Price,Rating,Q,Range):
# write your code here
# return a list of answers of Q queries
ans = {}
returnli = []
for i in range(len(Price)):
ans[Price[i]] = Rating[i]
for i in Range:
a = i[0]
b = i[1]
maxel = -1
for i in range(a, b+1):
if i in ans.keys():
maxel = max(maxel, ans[i])
if (i > max(ans.keys())):
break
returnli.append(maxel)
return returnli
```