潘多拉星球上的赛车比赛变得前所未有的流行。但这些比赛非常不同寻常。有 $n$ 辆赛车在一条笔直的长赛道上进行比赛。每辆赛车的速度均为每秒 $1$ 米。赛道坐标以米为单位。

第 $i$ 辆赛车在赛道上坐标为 $a_i$ 和 $b_i$ 的两个点之间往返运动，在 $0$ 秒时从 $a_i$ 点出发。赛车先从 $a_i$ 运动到 $b_i$，然后从 $b_i$ 运动到 $a_i$，再从 $a_i$ 运动到 $b_i$，以此类推。

帅气的迈克（Handsome Mike）想要用炸药淘汰一些赛车。因此，他提出了 $m$ 个问题。第 $j$ 个问题是：在 $t_j$ 秒后，坐标在 $[x_j, y_j]$（包含端点）范围内的赛车有多少辆？

你的任务是回答迈克的问题。

输入格式

输入文件的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 1000$)，分别表示赛车的数量和问题的数量。

接下来的 $n$ 行，每行包含一辆赛车的描述：两个整数 $a_i$ 和 $b_i$ ($0 \le a_i, b_i \le 10^9, a_i \neq b_i$)，表示第 $i$ 辆赛车往返运动的两个端点坐标。

接下来的 $m$ 行，每行包含一个问题的描述：三个整数 $x_j, y_j$ 和 $t_j$ ($0 \le x_j \le y_j \le 10^9, 0 \le t_j \le 10^9$)，表示第 $j$ 个问题的坐标范围和时间。

输出格式

输出 $m$ 行。每行包含一个整数，即按照输入顺序对应问题的答案。

样例

输入 1

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

输出 1

5
1
2
4
3