Counting Overlapping Intervals

You are given two sets of intervals: one representing matches and another representing queries. Each match is defined by its start and end time and each query is defined by a period. Two intervals overlap if they share at least one common point, i.e. for a match interval \((s, e)\) and a query interval \((q_s, q_e)\), they overlap if and only if \(q_s \le e\) and \(q_e \ge s\).

Your task is to compute, for each query, the number of match intervals that overlap with that query.

The input first consists of an integer \(N\) indicating the number of match intervals, followed by \(N\) lines each containing two integers representing the start and end of a match. Then an integer \(Q\) is given, followed by \(Q\) lines each containing two integers representing the start and end of a query interval.

The output should be a single line containing \(Q\) integers separated by spaces, where the \(i\)th integer is the count of matches overlapping with the \(i\)th query.

inputFormat

The input is read from standard input (stdin) and has the following format:

N
s1 e1
s2 e2
... 
sN eN
Q
q1_start q1_end
q2_start q2_end
... 
qQ_start qQ_end

Where \(N\) is the number of match intervals, each given by two integers \(s_i\) and \(e_i\), and \(Q\) is the number of queries, each given by two integers \(q_{i,start}\) and \(q_{i,end}\).

outputFormat

The output is read from standard output (stdout) as a single line consisting of \(Q\) integers separated by a space. Each integer represents the count of match intervals that overlap with the corresponding query.

## sample

1
1 4
1
2 3

1

</p>