Successful Pair Insertion

You are given \( n \) pairs \( (a_i, b_i) \) for \( 1 \le i \le n \). Initially, an empty stack \( S \) is maintained. When attempting to push a new pair \( (a_i, b_i) \) onto \( S \), you repeatedly pop the top element until either the stack becomes empty or the top element \( (a_j, b_j) \) satisfies the condition

[ \text{condition: } a_i \neq a_j \text{ and } b_i < b_j ]

After the popping process, the pair \( (a_i, b_i) \) is pushed onto the stack. A pair is called "successful" if, immediately after it is pushed, the stack contains exactly one element. You are also given \( q \) queries. In each query, you are given an interval \( [l, r] \), and you must consider only the pairs with indices from \( l \) to \( r \) (in increasing order) and simulate the stacking process (each query is independent, starting with an empty stack). Your task is to determine the number of successful pairs for each query.

inputFormat

The first line contains two integers \( n \) and \( q \) — the number of pairs and the number of queries respectively.

The next \( n \) lines each contain two integers \( a_i \) and \( b_i \), representing the pairs.

The following \( q \) lines each contain two integers \( l \) and \( r \) representing a query interval.

outputFormat

For each query, output a single integer on a new line — the number of successful pairs when the pairs in the corresponding interval \( [l, r] \) are processed in order.

sample

3 2
1 5
2 3
1 2
1 3
2 3

1
1