Product Search

Given a list of products with their types and prices, and a set of queries describing a type and a price range, your task is to determine the number of products that satisfy each query. For each query, you need to count the number of products whose type matches the query and whose price lies in the inclusive range [L, R].

Mathematically, for a given query with type T and range [L, R], you need to compute: [ \text{count} = \left|{ p \in P_T : L \leq p \leq R }\right| ] where (P_T) is the set of prices for products of type T.

inputFormat

Input is read from standard input (stdin). The first line contains two integers (N) and (Q), representing the number of products and the number of queries, respectively. The next (N) lines each contain a string and an integer: the product type and its price. This is followed by (Q) lines, each containing a string and two integers (L) and (R), representing a query.

outputFormat

For each query, output a single integer on a new line, representing the number of products that match the query criteria. The output should be written to standard output (stdout).## sample

6 2
book 15
book 20
pen 5
pen 7
pen 10
book 10
book 10 20
pen 5 10

3
3