题目描述

XRH在一个无限长的赛车跑道进行距离标记，起点标记为 $0$，之后每 $1$ 米都会进行标记。

现在有 $n$ 辆赛车在跑道上进行测试，第$i$ 辆赛车会在跑道$a_i∼b_i$ 段进行来回行驶：

• （1）先从 $a_i$ 向$b_i$ 行驶，即：$a_i→b_i$；

• （2）到达 $b_i$ 后，再从$b_i$ 向$a_i$ 行驶，即：$b_i→a_i$；

• 重复执行（1）、（2）。

已知每辆赛车的速度为$1m/s$，开始时（$0$ 时刻），第 $i$ 辆赛车位于$a_i$ 处，然后赛车同时开始行驶，赛车之间不会相互干扰。

现在XRH有$q$ 个问题，对于每个问题，XRH想要知道在$t$ 时刻时，赛道上$x∼y$ 内（包含位置 $x,y$）有多少辆赛车。

输入格式

第一行输入两个正整数$n,q$，表示赛车的数量和问题的数量。

接下来 $n$ 行，每行两个整数$a_i,b_i$，表示第$i$ 辆赛车在$a_i∼b_i$ 之间来回行驶。

接下来$q$ 行，每行三个整数$t,x,y$，表示每个问题中，XRH想要知道在 $t$ 时刻时，赛道上$x∼y$ 内（包含位置 $x,y$）有多少辆赛车。

输出格式

输出共$q$ 行，每行一个整数，第$i$ 个数表示第$i$ 个问题中，在$t$ 时刻时，赛道上$x∼y$ 内（包含位置$x,y$）赛车的数量。

格式说明

输出时每行末尾的多余空格，不影响答案正确性

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

5
1
2
4
3

样例解释

对于第一个问题，在 $0$时刻时，每辆车的位置如下图所示，区间$0∼5$ 内有$5$ 辆车：

对于第二个问题，在$2$ 时刻时，每辆车的位置如下图所示，区间$0∼1$ 内有 $1$ 辆车：

对于第三个问题，在$1$ 时刻时，每辆车的位置如下图所示，区间$0∼2$ 内有$2$ 辆车：

对于第四个问题，在$2$ 时刻时，每辆车的位置如下图所示，区间$2∼5$ 内有$4$ 辆车：

对于第五个问题，在$3$ 时刻时，每辆车的位置如下图所示，区间$2∼5$ 内有$3$ 辆车：

数据范围

对于$30\%$ 的数据，$1≤n,q≤100,0≤a_i<b_i≤100,0≤t≤100,0≤x<y≤100$；

对于$100\%$ 的数据，$1≤n,q≤1000,0≤a_i<b_i≤10^9,0≤t≤10^9,0≤x<y≤10^9$。