位于 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