Maximum Safe Tree Felling in a Query Range

An organization has received q logging requests. In each request, the applicant specifies two integers \(l_i\) and \(r_i\), meaning that they wish to fell trees numbered from \(l_i\) to \(r_i\) (inclusive). The trees are arranged in increasing order with positions \(x_1, x_2, \dots, x_n\) and each tree \(i\) has a height \(h_i\) (which is the length of the tree when felled).

When processing a request, only the trees with indices from \(l_i\) to \(r_i\) may be chopped; trees outside this range remain standing. A felled tree falls either completely to the left or completely to the right. Specifically:

• If a tree \(i\) is felled to the left, it occupies the interval \([x_i - h_i, x_i]\).
• If it is felled to the right, it occupies \([x_i, x_i + h_i]\).

The fallen tree must satisfy the following conditions:

1. The entire fallen interval must lie within the overall region \([x_1, x_n]\). That is, when felled to the left: \(x_i - h_i \ge x_1\); when felled to the right: \(x_i + h_i \le x_n\).
2. The fallen tree must not touch any tree outside the current request range. In other words, if there is a tree immediately to the left of the range (tree \(l_i-1\), if it exists) with position \(x_{l_i-1}\), then a tree in the range can be felled to the left only if \(x_i - h_i > x_{l_i-1}\). Similarly, if there is a tree immediately to the right (tree \(r_i+1\), if it exists) with position \(x_{r_i+1}\), then a tree in the range can be felled to the right only if \(x_i + h_i < x_{r_i+1}\).

Each tree in the range \([l_i, r_i]\) can be felled in at most one direction, and if at least one direction is safe the tree can be chopped. The task is to compute, for each request, the maximum number of trees (among the trees in the specified range) that can be chopped down without damaging any tree that is not part of the request.

Note: Each logging request is independent (i.e. even if a tree is chopped in one request, it is still standing for another request).

inputFormat

The input is given in the following format:

 n q
 x1 h1
 x2 h2
 ...
 xn hn
 l1 r1
 l2 r2
 ...
 lq rq

Where:

• \(n\) (\(\ge 1\)) is the total number of trees. The trees are given in increasing order of their positions \(x_i\).
• Each tree \(i\) has a position \(x_i\) and height \(h_i\) (both integers).
• \(q\) is the number of logging requests.
• Each request consists of two integers \(l_i\) and \(r_i\) (1-indexed) representing the range of trees the applicant wishes to fell.

outputFormat

For each logging request, output a single integer—the maximum number of trees in that range that can be safely felled.

sample

5 3
1 2
3 1
6 2
10 1
12 2
1 3
2 5
3 4

3
4
2