Depot Vehicle Movement Query

You are given a series of logs recording depot visits. Each log entry consists of two values: a depot number and a date in the format \(YYYY\text{-}MM\text{-}DD\). You are also given a series of queries. Each query consists of a depot number, a start date, and an end date.

Your task is to count the number of unique dates on which the specified depot was visited, where the visit date falls within the inclusive range of \(\text{start date}\) and \(\text{end date}\). Note that even if a depot has multiple logs on the same date, it should only be counted once for that date.

For example, if the depot 1 is visited on 2023-01-01 and again on 2023-01-01, it counts as a single unique date visit.

inputFormat

The input is provided via standard input (stdin) in the following format:

n q
log_1
log_2
... 
log_n
query_1
query_2
... 
query_q

Here, the first line contains two integers \(n\) and \(q\) representing the number of log entries and the number of queries, respectively. The next \(n\) lines each contain a log entry with a depot number and a date separated by a space. The following \(q\) lines each contain a query with a depot number, a start date, and an end date separated by spaces.

outputFormat

For each query, output a single integer on its own line — the number of unique dates on which the specified depot was visited within the inclusive date range.

## sample

5 3
1 2023-01-01
2 2023-01-02
1 2023-01-03
3 2023-01-02
1 2023-01-04
1 2023-01-01 2023-01-04
2 2023-01-02 2023-01-02
3 2023-01-01 2023-01-02

3
1
1

</p>