← 返回题目列表

Codeforces · 286/D

D. 游客

中文机器翻译题面 查看原题

位于 Ultima Thule 公园的双旅游道按照以下原则运行:

- 我们介绍笛卡尔坐标系。
- 在某些时间点,有两名游客同时从点 ( - 1, 0) 和 (1, 0) 出发(散步)。第一个是从( - 1, 0)开始走,第二个是从(1, 0)开始走。
- 一对游客均以相同的速度1(每秒距离单位)移动,第一个游客沿线x =  - 1移动,第二个游客沿线x = 1移动,两者均沿Oy轴正方向移动。
- 有时会出现墙壁。墙 (li, ri) 是点 (0, li) 和 (0, ri) 之间的线段。每面墙都会立即出现。

Ultima Thule 政府希望了解每对同时行走的游客:他们多久(以秒为单位)不会见面?如果连接平面上两个游客位置的线段与至少一堵墙相交,两个游客就看不到对方。如果两条线段至少共享一个点,则它们相交。我们假设段的末端属于段。

帮助政府计算所需时间。请注意,墙壁可以相交(以任何方式)或重合。

输入

第一行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 105) — 游客对的数量和已建墙的数量。接下来的 m 行包含三个空格分隔的整数 li、ri 和 ti(0 ≤ li < ri ≤ 109, 0 ≤ ti ≤ 109)——墙的结束和它出现的时间。最后一行包含 n 个不同的空格分隔的严格递增整​​数 q1, q2, ..., qn (0 ≤ qi ≤ 109) — 成对游客行走的时间点。

所有时间点均以秒为单位给出。

输出

对于每对游客,在一行上打印一个整数 - 相应对中的两名游客不会看到对方的时间(以秒为单位)。按照数字在输入中的顺序打印数字。

示例

输入 #1

2 2
1 4 3
3 6 5
0 1

输出 #1

2
4

输入 #2

3 3
0 3 4
0 1 2
2 4 0
1 3 4

输出 #2

2
4
4