Book Recommendations

You are given a list of books, where each book is described by a genre (a string) and a rating (an integer). Then, you are given a series of queries. Each query specifies a genre and a minimum rating requirement. For each query, determine how many books in that genre have a rating greater than or equal to the specified minimum rating.

More formally, let the list of books be represented as a sequence of pairs \((g, r)\), where \(g\) is the genre and \(r\) is the book's rating. Each query is a pair \((q, m)\) and you are to output the count of books satisfying \(g = q\) and \(r \ge m\).

Hint: You might want to use sorting and binary search for an efficient solution. In fact, after grouping the books by genre and sorting the ratings for each genre, you can use binary search to find the number of ratings that are \(\ge m\) using the standard lower bound technique.

The binary search condition can be mathematically described as finding the smallest index \(i\) in a sorted array \(A\) such that:

[ A[i] \ge m ]

Then, the answer for that query is \(|A| - i\), where \(|A|\) denotes the length of array \(A\).

inputFormat

The input is read from standard input. The first line contains a single integer \(n\) representing the number of books. The following \(n\) lines each contain a genre (string) and a rating (integer), separated by a space.

The next line contains a single integer \(q\) indicating the number of queries. Each of the next \(q\) lines contains a genre and a minimum rating (integer), separated by a space.

Input Format Example:

5
fiction 4
nonfiction 3
fiction 5
mystery 5
nonfiction 2
3
fiction 4
nonfiction 3
mystery 5

outputFormat

For each query, print the number of books (each on a new line) that satisfy the condition: the book's genre matches the query's genre and its rating is at least the query's minimum rating.

Output Format Example:

2
1
1

## sample

5
fiction 4
nonfiction 3
fiction 5
mystery 5
nonfiction 2
3
fiction 4
nonfiction 3
mystery 5

2
1
1

</p>