CF286D Tourists

乌尔蒂马·图勒公园内有一条双人旅游步道，其运行方式如下： - 我们建立一个笛卡尔坐标系。 - 在某些时刻，会有两位游客分别从 $(-1,0)$ 和 $(1,0)$ 同时出发开始散步。第一位游客从 $(-1,0)$ 出发，第二位游客从 $(1,0)$ 出发。 - 一对游客均以相同的速度 $1$（单位距离每秒）运动，第一位游客沿 $x=-1$ 直线移动，第二位游客沿 $x=1$ 直线移动，两人均沿 $Oy$ 轴的正方向前进。 - 在某些时刻，会出现一些墙壁。第 $i$ 道墙是由点 $(0, l_{i})$ 到 $(0, r_{i})$ 之间的线段，每堵墙的出现是瞬时的。 乌尔蒂马·图勒的政府想要知道，对于每对同一时间出发的游客来说，他们将有多少秒“看不见彼此”。如果连接两人当前位置的线段与至少一堵墙相交，则认为他们相互看不见（两个线段有公共点即为相交，线段的端点算在线段之上）。 请帮助政府统计每一对游客由于被墙阻隔而互相看不见的时间。注意，不同的墙之间可以相交或者重合。

第一行包含两个空格分隔的整数 $n$ 和 $m$（$1 \leq n, m \leq 10^{5}$），表示游客对数和墙的数量。接下来的 $m$ 行，每行包含三个空格分隔的整数 $l_{i}$、$r_{i}$ 和 $t_{i}$（$0 \leq l_{i} < r_{i} \leq 10^9$，$0 \leq t_{i} \leq 10^9$），表示第 $i$ 道墙覆盖的 $y$ 区间及其出现的时刻。最后一行包含 $n$ 个严格递增的整数 $q_1,q_2,...,q_n$（$0 \leq q_i \leq 10^9$），表示每对游客出发的时刻。 所有时刻均以秒为单位。

对于每一对游客，请输出一行一个整数，表示对应游客看不见彼此的时间（秒数）。输出顺序与输入顺序一致。

由 ChatGPT 5 翻译