你有一个整数 $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′$ 时刻末之前的限制即可）。

第一行一个整数 $T（1≤T≤600）$，表示测试数据的组数。

对于每组数据，第一行两个整数 $n$ 和 $q（1≤n,q≤5×10^5 ）$，分别表示限制个数和询问个数。

接下来 $n$ 行，第 $i$ 行三个整数 $t_i,l_i,r_i（1≤t_i ≤10^9,−10^9≤l_i≤r_i≤10^9）$，分别表示限制的时刻和限制范围。保证满足 $1≤t_1\lt t_2\lt …\lt t_n≤10^9$ 。

接下来一行 $q$ 个整数 $t_1', t_2',..., t_q' (1 \le t_1' \lt t_2', \lt ... \lt t_q' \le 10^9)$，依次表示第 $1$ 到第 $q$ 个询问的时刻。

保证所有测试数据的 $n$、$q$ 之和均不超过 $10^6$ 。

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