数字加减

Problem Description

你有一个整数 $s$，初始时 $s = 0$。每秒钟你可以在以下两个操作中选择执行至多一个：$s := s + 1$ 或 $s := s - 1$（可以不执行任何一个）。$s$ 需要满足 $n$ 个限制，第 $i$ 个限制是在 $t_i$ 时刻末 $s$ 不能在 $[l_i, r_i]$ 范围内。 你需要回答 $q$ 个询问，第 $i$ 次询问给出一个时刻 $t'_i$，你需要回答第 $t'_i$ 时刻末在满足限制的情况下 $s$ 有多少种可能的取值（只需要考虑 $t'_i$ 时刻末之前的限制即可）。

Input

第一行一个整数 $T$（$1 \le T \le 600$），表示测试数据的组数。 对于每组数据，第一行两个整数 $n$ 和 $q$（$1 \le n,q \le 5 \times 10^5$），分别表示限制个数和询问个数。 接下来 $n$ 行，第 $i$ 行三个整数 $t_i,l_i,r_i$（$1\le t_i\le 10^9,-10^9 \le l_i \le r_i \le 10^9$），分别表示限制的时刻和限制范围。保证满足 $1 \le t_1 < t_2 < \ldots < t_n \le 10^9$。 接下来一行 $q$ 个整数 $t'_1, t'_2, \ldots, t'_q$（$1 \le t'_1 < t'_2 < \ldots < t'_q \le 10^9$），依次表示第 $1$ 到第 $q$ 个询问的时刻。 保证所有测试数据的 $n$、$q$ 之和均不超过 $10^6$。

Output

对于每组测试数据，输出一行 $q$ 个整数，第 $i$ 个整数表示第 $i$ 个询问的答案。

Sample Input

2
2 3
3 -1 1
5 -2 0
2 3 5
2 2
4 -2 2
5 -10 10
3 5

Sample Output

5 4 8
7 0

Source

2024“钉耙编程”中国大学生算法设计超级联赛（6）