Optimal Transfer

Capacities are in ascending order and distinct. A direct connection between any two servers costs the difference of their capacities, and connecting to the nearest server costs 1. Answer 0-based queries.

See "Input" for the standard input/output conventions and constraints added by this site.

输入格式

n,q≤200000, capacity≤10^9, and each server's nearest server is unique.

输出格式

Output the minimum connection cost for each query in order.

样例 1

输入：

3 3
2 7 10
0 1 2
2 2 1

输出：

2 1 1

样例 2

输入：

4 3
1 4 9 15
0 3 1
3 0 3

输出：

12 3 11

样例 3

输入：

3 2
5 6 20
2 0
0 1

输出：

2 1