CDR 的抓娃娃机 1659

Time Limit: 1 Sec Memory Limit: 256 MB

Submission：34 AC：11 Score：100

Description

CDR 最近很喜欢玩一款特殊的抓娃娃机

这台抓娃娃机的平台可以看作是一条很长的数轴，最左端是 $0$，每隔一定距离进行一次标记编号（1,2,3,4...)

平台上共有 $n$ 个玩偶，每个玩偶会在某个区间内来回来回移动，例如对于第 $i$ 个玩具，它会在 $[x_i,y_i]$ 这个编号区间内来回移动，移动速度 $1$单位$/s$

也就是说对于第 $i$ 个玩具来说
第 $0$ 时刻，它会在 $x_i$ 位置，接着向 $y_i$ 移动
在经过一段时间到达 $y_i$ 以后，改向 $x_i$ 移动
如此往复

现在 CDR 想知道，她在 $T$ 时刻用爪子抓起区间 $[l,r]$ 内的所有娃娃，会有多少个？

CDR 共有 $q$ 次这样的询问，请你帮帮她

P.S. 这里我们认为所有娃娃不会互相影响，即允许很多娃娃同时处于某个编号点

Input

输入第一行包含两个整数 $n, q$，含义如题
接下来 $n$ 行，每行包含两个整数 $x_i,y_i$，表示第 $i$ 个娃娃移动的区间
接下来 $q$，每行包含两个整数 $l_i, r_i, T$，表示 CDR 第 $i$ 次的询问

对于 $30\%$ 的数据：$1 \leq n,q \leq 100, 0 \leq x_i < y_i \leq 100, 0 \leq l_i < r_i \leq 100, 0 \leq T \leq 100$
对于 $100\%$ 的数据：$1 \leq n,q \leq 1000, 0 \leq x_i < y_i \leq 10^9, 0 \leq l_i < r_i \leq 10^9, 0 \leq T \leq 10^9$

Output

输出共 $q$ 行，每行一个整数，对于每一次 CDR 的询问，给出结果

Samples

input:

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

output:

5 1 2 4 3