Minimum Segments Covering Problem

There is a number line from 1 to n and m colors of segments. For the i-th color, only the subsegment \( [l_i, r_i] \) of the number line may be covered by segments of that color, and any segment of that color can have a length of at most \( k_i \) (with \( k_i \le 10 \)). You can use any number of segments (even many segments of the same color).

You will be given q queries. In each query, two integers a and b are provided, and your task is to determine the minimum number of segments needed to cover the interval \( [a, b] \) completely. It is guaranteed that every position on the number line is coverable by at least one segment of some color.

Note: When placing a segment of color i to cover a portion of the interval \( [a, b] \), the entire segment must lie within \( [l_i, r_i] \) and its length cannot exceed \( k_i \). The optimal strategy is typically to use segments that extend as far to the right as possible.

inputFormat

The first line contains two integers n and m.

Each of the next m lines contains three integers \( l_i \), \( r_i \), and \( k_i \) (with constraints \( 1 \le l_i \le r_i \le n \) and \( 1 \le k_i \le 10 \)).

The next line contains a single integer q representing the number of queries.

Each of the following q lines contains two integers a and b (\( 1 \le a \le b \le n \)), representing a query asking for the minimum number of segments required to cover the interval \( [a, b] \).

outputFormat

For each query, output a single integer representing the minimum number of segments needed to cover the interval \( [a, b] \).

sample

10 2
1 10 3
2 8 2
3
1 10
2 5
4 10

4
2
3