题目描述

组织“2D”负责签发沿公路砍树的许可。公路旁共有 $n$ 棵树，第 $i$ 棵树生长在坐标 $x_i$ 处，高度为 $h_i$。树的信息按坐标递增给出，即：

树可以一棵一棵砍倒。砍树时，树会被从根部砍断，然后必须向左或向右倒下。为了保证树倒下时不被损坏，它不能碰到尚未砍倒的其他树。

更准确地说：

• 若坐标为 $x_i$、高度为 $h_i$ 的树向右倒，则不能存在尚未砍倒的树 $x_j$ 满足

• 若这棵树向左倒，则不能存在尚未砍倒的树 $x_j$ 满足

在最左边树 $x_1$ 左侧和最右边树 $x_n$ 右侧有重要建筑，因此树不能倒到区间 $[x_1,x_n]$ 外。也就是说：

• 如果 $x_i-h_i<x_1$，则第 $i$ 棵树不能向左倒；
• 如果 $x_i+h_i>x_n$，则第 $i$ 棵树不能向右倒。

第一个样例中，先把第二棵树向右倒，再把第三棵树向左倒，最后把第一棵树向右倒。整理为 Markdown 时此处可插入原 PDF 第 6 页的图。

现在有 $q$ 个砍树申请。每个申请由两个数 $l_i,r_i$ 给出，表示申请者只想砍编号从 $l_i$ 到 $r_i$ 的树。

处理一个申请时，只允许砍编号在 $[l_i,r_i]$ 内的树。砍倒的树可以倒到编号 $l_i$ 左侧或编号 $r_i$ 右侧的区域，但仍然不能倒出整个区间 $[x_1,x_n]$，也不能碰到编号不在 $[l_i,r_i]$ 中、尚未被砍的树。

对每个申请，要求计算在不损坏任何树的前提下，最多可以砍掉多少棵编号在该区间内的树。每个申请相互独立。

输入格式

第一行包含两个整数 $n,q$。

接下来 $n$ 行，每行包含两个整数 $x_i,h_i$，表示第 $i$ 棵树的位置和高度。

保证：

接下来 $q$ 行，每行包含两个整数 $l_i,r_i$，表示一个申请。

输出格式

对每个申请输出一行，表示最多可以砍掉的树的数量。

数据范围

样例 1 输入

3 3
1 3
3 1
4 2
1 1
2 3
1 3

样例 1 输出

0
2
3

样例 2 输入

5 3
1 5
3 1
4 2
5 3
6 1
1 5
5 5
1 1

样例 2 输出

5
1
0

样例 3 输入

1 1
100 100
1 1

样例 3 输出

0

子任务

第 7 个子任务包含 30 个测试点，每个测试点独立计 1 分。只有当前六个子任务全部通过后，才会测试第 7 个子任务。