题目描述

有 $n$ 个区间，第 $i$ 个区间是 $[l_i,r_i]$，它的长度是 $r_i-l_i$。

有 $q$ 个询问，每个询问给定 $L,R,K$，询问被 $[L,R]$ 包含的且长度不小于 $K$ 的区间数量。

你想，像这种板子题，你随手写，不到十分钟就能 AC。

输入格式

从文件 original.in 中读入数据。

第一行，两个空格隔开的正整数 $n,q$。

接下来 $n$ 行，第 $i$ 行有两个空格隔开的正整数 $l_i,r_i$。

接下来 $q$ 行，每行三个空格隔开的正整数 $L,R,K$，表示一个询问。

输出格式

将答案输出到文件 original.out 中。

共 $q$ 行，每行一个非负整数，表示询问的答案。

样例

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

5
4
3
2
1

样例解释

第 $1$ 个询问中，$5$ 个区间都包含在 $[1,5]$ 内，且长度都不小于 $1$，答案为 $5$。第 $5$ 个询问中，只有区间 $[2,5]$ 的长度不小于 $3$，答案为 $1$。

数据范围

对于 $30\%$ 的数据，$n,q\leq 5{,}000$；

对于 $60\%$ 的数据，$n,q\leq 50{,}000$；

对于所有数据，$n,q\leq 500{,}000$，$l_i,r_i,L,R,K\leq n$，$l_i<r_i$，$L<R$。