Question

$79$

Max. score: $20\mathrm{.}00$

Tax payment

Problem statement

You are a manager in an office and keep a track of all the N employees in the office. In an excel sheet, there are N rows and $2$ columns wherein the ith row $1$st column denotes the id of the ith employee and $2$nd column denotes the salary of the ith employee. The contents of the excel sheet are described by a $2$D array A of size N$*2.$

Task

You are given Q queries where each query is denoted by parameters l$,$r$,$x$.$ Each employee with a salary strictly greater than x needs to pay tax. You are asked to filter out the rows in the range l to r where employees will pay the tax. The answer to the query will be the number of rows left in the excel sheet after applying the given filter.

Note:$-$

The queries are independent i$.$e$.$ the changes$($filtering$)$ made in the excel sheet in the previous queries will not be persisted.

The id numbers of all employees are distinct integers from $1$ to N$.$

Example

Assumptions

N $=5$

A $=[[1,1],[2,2],[3,2],[4,3],[5,5]]$

queries $=[[1,5,2],[2,4,1]]$

Approach

In the $1$st query, only the $4$th and $5$th employees in the given range have salaries greater than $2.$So the number of rows left after applying the filter in the excel sheet is $2.$

In the $2$nd query, all three employees in the given range have salaries greater than $1.$ So the number of rows left after applying the filter in the excel sheet is $3.$

Function Description

Complete the filter function provided in the editor. This function takes the following $3$ parameters and returns the array of integers of size Q which represents the answer to the queries as described above in the problem statement.

N: represents the number of rows in the excel sheet.

A: represents a $2$D array containing the id and the salary of the N employees.

queries: represents an array of size Q which denotes the query parameters l$,$r$,$x$.$

Input Format

Note: This is the input format that you must use to provide custom input $($available above the$$Compile and Test$$button$).$

The first line contains N$,$ the$$size of the function parameter A$.$

The next N lines contain two$$space$-$separated integers denoting the id and the salary of the N employees.

The second line contains the number of queries Q$$i$.$e the size of function parameter queries.

The next Q lines contain three space$-$separated integers$$

$$

$,$

$$

$,$

$$

$.$

Output format

Print Q space$-$separated integers where each integer represents the answer to each query.

Constraints

$1$

$<=$

$$

$,$

$$

$<=$

$10$

$5$

$1$

$<=$

$$

$$

$$

$<=$

$$

$1$

$<=$

$$

$$

$$

$$

$$

$$

$$

$,$

$$

$<=$

$10$

$9$

$1$

$<=$

$$

$<=$

$$

$<=$

$$

Code snippets $($also called starter code$/$boilerplate code$)$

This question has code snippets for C$,$ CPP$,$ Java, and Python.

Sample input

$5$

$11$

$22$

$32$

$43$

$55$

$2$

$152$

$241$

Sample output

$23$

Explanation

For the given sample input$$

Given

N $=5$

A $=[[1,1],[2,2],[3,2],[4,3],[5,5]]$

queries $=[[1,5,2],[2,4,1]]$

Approach

In the $1$st query, only the $4$th and $5$th employees in the given range have salaries greater than $2.$So the number of rows left after applying the filter in the excel sheet is $2.$

In the $2$nd query, all three employees in the given range have salaries greater than $1.$ So the number of rows left after applying the filter in the excel sheet is $3.$

$$

The following test cases are the actual test cases of this question that may be used to evaluate your submission.

Sample input $1$

$71$

$143$

$27$

$364$

$424$

$514$

$630$

$717$

$824$

$989$

Sample output $1$

$29193211901121054851711220017016804227001163695304725104610001500215051181244135510$

View more

Sample input $2$

$613$

$17538$

$22225$

$34638$

$45798$

$59842$

$66296$

$72132$

$88640$

$9203$

Sample output $2$