Active Users Query with Timestamps

You are given a list of user records and a set of queries. Each record consists of a user ID (a string) and a timestamp (an integer). A query specifies a time interval \( [a, b] \). For each query, your task is to count the number of unique users who have a record with a timestamp \( t \) satisfying \( a \le t \le b \).

Note: The input is provided through standard input (stdin) and the output should be printed to standard output (stdout). The problem can be formally stated as:

[ \text{answer} = \left|{ u : \exists t ;\text{such that}; (u, t) \text{ is a record and } a \le t \le b }\right| ]

inputFormat

The first line contains two integers \( n \) and \( m \): the number of user records and the number of queries, respectively.

The next \( n \) lines each contain a string and an integer, representing a user ID and a timestamp.

The following \( m \) lines each contain two integers \( a \) and \( b \), representing a query interval \( [a, b] \).

outputFormat

For each query, output a single line containing the number of unique users who have at least one record with a timestamp in the query interval \( [a, b] \).

## sample

2 3
user1 10
user1 20
5 15
10 20
15 25

1
1
1

</p>