Description

在 Pandora 星球上，比赛比以往任何时候都更受欢迎。但这些比赛相当不寻常。有 $n$ 辆车在一条长直赛道上参加比赛。每辆车以每秒 1 米的速度移动。赛道的坐标以米为单位。

第 $i$ 号车在赛道上两个坐标为 $a_{i}$ 和 $b_{i}$ 的点之间移动，起始于第 0 秒在点 $a_{i}$。车从 $a_{i}$ 移动到 $b_{i}$，然后从 $b_{i}$ 移动到 $a_{i}$，然后再从 $a_{i}$ 移动到 $b_{i}$，如此往复。

英俊的 Mike 想用炸药将一些车淘汰出比赛。因此他有 $m$ 个问题。第 $j$ 个问题是：从开始到 $t_{j}$ 秒后，坐标在 $x_{j}$ 到 $y_{j}$ 之间（包括边界）的车的数量是多少？

你的任务是回答 Mike 的问题。

Input Format

输入文件的第一行包含两个整数 $n$ 和 $m$ $(1 \le n , m \le 1000)$ —— 比赛中的车的数量和问题的数量。

接下来的 $n$ 行中的每一行包含一辆车的描述：两个整数 $a_{i}$ 和 $b_{i}$ $(0 \le a_{i}, b_{i} \le 10^{9}, a_{i} eq 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$ 的坐标范围和时间。

Output Format

将 $m$ 行写入输出文件。每行必须包含一个整数 —— 按输入文件中给出的顺序对应问题的答案。

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

5
1
2
4
3

Hint

时间限制：1 秒，内存限制：256 MB。

题面翻译由 ChatGPT-4o 提供。