蚂蚁财富

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

 

n只蚂蚁以每秒1cm的速度在长为L(cm)的竿子上爬行。当蚂蚁爬到竿子的端点时就会掉落。由于竿子太细,两只蚂蚁相遇时,它们不能交错通过,只能各自反向爬回去。对于每只蚂蚁,我们知道它距离竿子左端的距离xi,但不知道它当前的朝向。请计算所有蚂蚁落下竿子所需的最短时间和最长时间。

Input

首先输入测试数据的组数t,后面是t组测试数据。

 

对于每组测试数据:

第一行是 两个正整数 L 和 N 分别表示竿子的长度L(cm)和驻留在竿子上的蚂蚁的数量n。  

 

第二行是n个正整数,给出了每个蚂蚁在杆上的位置(即离杆最左端的距离 )。所有输入的正整数都不大于1000000。

Output

对于每种情况的输入,输出由一个空格分隔的两个数字。第一个数字是所有蚂蚁从竿上掉下来的最早时间(如果他们的行走方向是适当选择的),第二个数字是 所有蚂蚁从竿上掉下来的最晚时间 。

Sample Input

2
10 3
2 6 7
214 7
11 12 7 13 176 23 191

Sample Output

4 8
38 207

Hint

Source

【2018年ACM寒假结训赛(2017级)】郭小冉