题目描述

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

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

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

输入格式

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

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

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

输出格式

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

样例

input

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

output

5
4
3
2
1

数据范围与提示

对于 $30\%$ 的数据，$n,q\leq5,000$；

对于 $60\%$ 的数据，$n,q\leq50,000$；

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